無線傳感器網絡中一種基于標記的能量平衡路由*

侯貴升， 吳曉蓓， 黃 成， 徐志良

(南京理工大學 自動化學院，江蘇 南京 210094)

0 引 言

近年來，隨著數據中心存儲、分布式數據庫等應用的興起[1]，適于無線傳感器網絡(wireless sensor networks,WSNs)的點對點路由越來越受到關注[2～5]。不同于傳統數據會聚路由，點對點路由允許任意節點間自由通信，不僅能實現數據會聚，還能為分布式存儲與查詢、非固定用戶訪問等多源多中心的應用模式提供支持。

WSNs以數據為中心,根據時延要求和流量特性可將網絡中的數據分為緊急和平常兩大類。緊急數據流多產生于緊急任務執行或控制消息傳輸，其單次任務的數據量較小、通信開銷低、能耗低，而對端到端時延敏感，要求傳輸路徑愈短愈好；而平常數據流則多產生于常規性任務執行或完整、詳實數據傳輸，對時延要求相對寬松，其單次任務的數據量較大、通信開銷高、能耗高，若只考慮路由效率容易形成局部“熱點”，不僅造成網絡擁塞影響緊急數據的傳輸，還會導致“熱點”區域內的節點因過載“早死”而使網絡生命期大為縮短。所以，對于平常數據的傳輸，需要兼顧轉發節點的負載和剩余能量情況，以均衡鏈路的使用和節點能耗，從而避免“熱點”的形成。

已有的研究中，文獻[3]提出了一種基于鄰居信息量化的能量平衡路由，較好地解決了貪婪地理路由過分使用最短路徑的問題。文獻[4]和文獻[5]各自通過構建一個反映節點間相對位置關系并能指導數據路由的虛擬標記系統，避免傳統地理路由對節點精確物理位置的依賴，降低成本的同時取得與其相似的性能。不過，兩者均未考慮節點的剩余能量和網絡擁塞。文獻[6]提出了一種基于由節點梯度和緩沖隊列占空比復合而成的勢場的實時路由，它能最小化數據時延，同時緩解網絡擁塞，但沒有考慮節點剩余能量。文獻[7]對此作了相應改進，不過，兩者均為數據會聚路由，不適合點對點的路由模式。

為此，本文提出一種基于標記的能量平衡(label-based energy-balanced,LBEB)路由。其基本思想：在網絡中嵌入多棵獨立樹，并以文獻[5]中介紹的區間標記法標記節點，由此，構建起一個多樹交疊但又彼此獨立的樹型標記系統，然后在此基礎上進行路由設計。對于緊急數據，采用貪婪轉發；而對于平常數據則綜合考慮鄰居節點的負載和剩余能量情況，從中選擇能量負載比最高的節點作為下一跳節點，以減少擁塞并均衡網絡能耗。

1 標記系統

考慮一個完全覆蓋監測區域并良好連通的傳感器網絡，網絡中的節點通過雙邊無線通信鏈路彼此連通。應用圖嵌入技術[4]向網絡中嵌入數棵獨立的最短路徑樹(shortest path tree,SPT)，然后參考節點間的相對位置關系，采用區間路由標記法對圖中的節點進行順序標記。

1.1 標記系統的建立

1)構建SPT:采用某類啟發機制[4]順序選擇m(m≥2)個節點作為SPT的根節點,然后令其分別廣播載有自身信息并包含跳數域的“HELLO”消息,其它節點對于源自同一根節點的“HELLO”消息只轉發一次，并將其當前跳數作為自身距離相應根節點的距離。當節點收集到所有根節點廣播的“HELLO”消息后，即可構建SPT：記根節點RT-i構建的SPT為SPT-i，其父節點為空，其它節點父節點的選擇原則：a.距離RT-i的跳數比自身小1；b,距離RT-j(i

2)反饋子樹大小:子樹大小是指以某節點為根的子樹中包含的節點數目，包括子樹根節點自身。該過程從葉節點開始，一直持續到根節點，最終使得根節點獲得整個樹的大小，而父節點獲得各個子節點子樹大小。

3)標記分配:設節點總數即整棵樹的大小為n，對于SPT-i，RT-i的相應區間標記為[1,n]，其子節點區間標記的分配原則：a.區間長度等于子節點子樹大??；b.分配次序由子節點到RT-j(j的取值與第一步相同)的距離跳數的升序決定。分配結果連同自身標記區間向鄰居節點廣播，分配過程遞推到葉節點為止。分配過程結束后，每個節點都獲得了m段標記區間，將其按所屬SPT的序號依次串接后，即可得到節點的完整標記，同理可得鄰居節點的完整標記。

1.2 標記性質

記L(A)-i為節點A的第i段標記區間，設其值為[p,q]，則q≥p，且根據標記區間的分配原則可知，該區間在SPT-i上唯一，p可作為節點在其上的特征編號。若p=1，則A為SPT-i的根節點；若p>1,且q=p，則A為葉節點；否則，A為中間節點；另外，q-p+1表示A子樹大小。

設L(A)-i,L(B)-i分別表示A,B兩節點的第i段標記區間，若L(A)-i覆蓋L(B)-i，則B在A子樹上；若兩者相交為空，則A不在B子樹上且B亦不在A子樹上，兩者在SPT-i上相互獨立。對于自然數i，i≤m，m為根節點數，有如下定義：

定義1 包含：若存在i使得L(A)-i覆蓋L(B)-i，則稱A包含B。

定義2 獨立：若L(A)-i與L(B)-i相交為空，對于所有i均成立，則稱A與B相互獨立。

定義3 RID：節點在SPT-1上的特征編號，能輔助數據路由。

2 LBEB算法設計

LBEB使用標記系統完成數據路由，同時，為平衡路由效率、時延要求和網絡能耗， 對于不同類型的數據采用不同的路由策略：緊急數據使用貪婪策略；平常數據使用平衡策略。

2.1 貪婪策略

依據1.1節區間標記的分配原則，不同節點S,D間的標記距離可定義如下

LD(i)，LS(i)分別表示D和S第i段有覆蓋關系的標記區間的長度；ND(i)，NS(i)分別表示D和S在SPT-i上的特征編號，m為根節點數。

貪婪策略：總是選擇與目的節點標記距離最小的節點作為轉發節點，若遭遇路由空洞即找不到比自己距離目的節點更近的轉發節點，則選擇SPT-1進行上溯(父節點作為轉發節點)，直到當前節點或其鄰居節點包含目的節點或被目的節點包含。

2.2 平衡策略

平衡策略需要綜合考慮轉發節點與目的節點的標記距離、剩余能量以及未來一段時間內的負載情況，然后在此基礎之上從距離目的節點更近的可選鄰居節點集或候選轉發節點集中選擇能量負載比最高者作為下一跳節點。

記Nb為節點的鄰居集，Sc為候選轉發節點集，c為候選系數，三者間的關系如下：

|Sc|=[c|Nb|]+，0

Sc的構造原則如下：1)包含關系優先；2)同優先級中，與目的節點標記距離小者優先；3)到目的節點的標記距離小于當前節點；4)若Sc為空，選擇SP-1進行上溯，直到當前節點或其鄰居節點包含目的節點或被目的節點包含。

同時，為估計未來一段時間Tw內節點的負載情況，節點需記錄上一個Tw內的負載，然后利用指數加權移動平均法進行預估

Qk=(1-a)Qk-1+aQ(k-1),01.

其中，Qk-1和Q(k-1)分別表示第k-1個Tw時段內節點負載的估計值和觀察值，而a為加權系數，決定預估計算法中最近一次觀察值的權重。記節點當前剩余能量為E，那么節點在第k個Tw內的能量負載比R(k)=E/Qk。R(k)的值通過周期性(周期為Tw)報文廣播通知鄰居節點，作為平衡策略從候選轉發節點集Sc中選擇轉發節點的依據(選擇其中R(k)值最高的節點作為轉發節點)。

3 仿真分析

使用OMNET++對LBEB進行仿真，主要參數：部署區域為300 m×300 m；通信半徑為30 m；平均鄰居數為15；候選系數c和加權系數a分別為0.6和0.5；節點初始能量為1 000個單位，發送一個緊急數據包和一個平常數據包分別消耗1個和4個能量單位。接收狀態能耗與空閑偵聽類似，忽略不計。

3.1 路由效率對比消息開銷

LBEB的性能與SPT數直接相關，圖1顯示了不同SPT數下緊急數據包的平均路徑長度比和構建標記系統時的總消息開銷：隨著SPT數增加，平均路徑長度比逐漸減小，其幅度呈現出先快后慢的趨勢，而消息開銷基本上是線性增長。其原因在于：SPT數增加，節點間的包含關系增加，而包含關系為確定性關系，彼此都能以最短路徑到達對方，同時，局部區域內節點間的順序性也會相應增加，從而使相互獨立的節點間能以較短路徑通信。不過，當SPT數達到一定值后，節點間的包含關系和順序性將趨于穩定，再增加SPT，對于路由效率的提升意義不大；另一方面，由于各個SPT間相互獨立，因而，構建標記系統的總消息開銷隨SPT數的增加呈線性增長，相應的，節點的標記長度亦呈類似增長。因而，需要在路由性能和開銷間尋找一個平衡點。注意到當SPT數到達5后，平均路徑長度比的減小速度明顯放緩，所以，本文之后的仿真均取SPT數為5。

圖1 平均路徑長度比和消息開銷

3.2 緊急數據包的端到端延遲

緊急數據對時延敏感， 圖2顯示了不同平常數據率下緊急數據包的端到端延遲隨網絡區域增大而變化的情況。網絡區域增大，任意節點間通信的平均最短路徑增加，數據包端到端平均延遲隨之增大；同時，平常數據率增大(數據包發送間隔Interval減小)，網絡負載明顯增加，在通信帶寬有限情況下，單跳通信的平均時間相應增加，數據包平均端到端延遲自然隨之增加。

圖2 緊急數據包的端到端延遲

3.3 網絡生命期

LBEB采用平衡策略轉發平常數據包，兼顧轉發節點的剩余能量情況以最大化網絡生命期。圖3顯示了不同平常數據所占比例下平衡策略(Balance)和貪婪策略(Gree-dy)對于不同生命期系數(失效節點所占比例)的網絡生命期。隨著平常數據所占比例增加，總數據量增加，總能耗增加，網絡生命期會相應減小，貪婪策略(針對所有數據包)還會加劇這種趨勢，因而其網絡生命期曲線呈現出加速下降的走勢；相反，對于平衡策略(僅針對平常數據包)而言，隨著平常數據所占比例增加，采用該策略的節點數所占比例會相應增加，從而在一定程度上緩解網絡生命期的減小趨勢，其網絡生命期曲線呈現出逐漸向上而后又向下的走勢，向下的原因在于平衡策略已經覆蓋網絡中的絕大多數節點。

圖3 網絡生命期比較

4 結束語

本文提出LBEB算法用以解決WSNs中數據的高效傳輸與網絡生命期的最大化。首先，應用圖嵌入式技術在網絡中嵌入多棵獨立最短路徑樹，并由此構建起一個不依賴節點物理位置的虛擬標記系統；然后，基于此標記系統設計了針對不同數據類型的轉發策略，在滿足數據時延要求的同時均衡節點負載和能耗，從而實現數據的高效傳輸與網絡生命期的最大化；最后，通過路由效率對比消息開銷、緊

急數據包的端到端延遲以及網絡生命期3個仿真實驗驗證了LBEB算法的有效性；不過，LBEB算法只適用于靜態網絡或弱動態網絡，加入動態性支持是進一步研究的一個方向，即節點失效或新節點加入后如何平穩、快速地對標記系統加以調整。

參考文獻:

[1] 蔚趙春,周水庚,關佶紅.無線傳感器網絡中數據存儲與訪問研究進展[J].電子學報,2008,36(10):2001-2010.

[2] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥6th Annual Int’l Conf on Mobile Computing and Networking,Boston:ACM,2000:243-254.

[3] 陳 衡,錢德沛,伍衛國.傳感器網絡基于鄰居信息量化的能量平衡路由[J].西安交通大學學報,2012,46(4):1-6.

[4] Newsome J,Song D.GEM:Graph embedding for routing and data-centric storage in sensor networks without geographic informa-tion[C]∥Proc of the 1st ACM Conference on Embedded Networked Sensor Systems(SenSys’03),Redwood,CA,USA:ACM,2003:76-88.

[5] 李志剛,陳衛衛,肖 儂,等.無線傳感器網絡中基于網絡嵌入的弱貪婪路由協議[J].通信學報,2011,32(12):88-95.

[6] Xu Y S,Ren F Y,He T,et al.Building a potential field to provide real-time transmission in wireless sensor networks[C]∥Proceedings of the 13th ACM International Conference on Modeling,Analysis and Simulation of Wireless and Mobile Systems,New York,USA:ACM,2010:403-410.

[7] 梁慶偉,姚道遠,鞏思亮.一種保障時延能量高效的無線傳感器網絡路由協議[J].西安交通大學學報,2012,46(6):48-53.