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

(南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094)

0 引 言

近年來，隨著數(shù)據(jù)中心存儲、分布式數(shù)據(jù)庫等應(yīng)用的興起[1]，適于無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的點(diǎn)對點(diǎn)路由越來越受到關(guān)注[2～5]。不同于傳統(tǒng)數(shù)據(jù)會(huì)聚路由，點(diǎn)對點(diǎn)路由允許任意節(jié)點(diǎn)間自由通信，不僅能實(shí)現(xiàn)數(shù)據(jù)會(huì)聚，還能為分布式存儲與查詢、非固定用戶訪問等多源多中心的應(yīng)用模式提供支持。

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

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

為此，本文提出一種基于標(biāo)記的能量平衡(label-based energy-balanced,LBEB)路由。其基本思想：在網(wǎng)絡(luò)中嵌入多棵獨(dú)立樹，并以文獻(xiàn)[5]中介紹的區(qū)間標(biāo)記法標(biāo)記節(jié)點(diǎn)，由此，構(gòu)建起一個(gè)多樹交疊但又彼此獨(dú)立的樹型標(biāo)記系統(tǒng)，然后在此基礎(chǔ)上進(jìn)行路由設(shè)計(jì)。對于緊急數(shù)據(jù)，采用貪婪轉(zhuǎn)發(fā)；而對于平常數(shù)據(jù)則綜合考慮鄰居節(jié)點(diǎn)的負(fù)載和剩余能量情況，從中選擇能量負(fù)載比最高的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，以減少擁塞并均衡網(wǎng)絡(luò)能耗。

1 標(biāo)記系統(tǒng)

考慮一個(gè)完全覆蓋監(jiān)測區(qū)域并良好連通的傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過雙邊無線通信鏈路彼此連通。應(yīng)用圖嵌入技術(shù)[4]向網(wǎng)絡(luò)中嵌入數(shù)棵獨(dú)立的最短路徑樹(shortest path tree,SPT)，然后參考節(jié)點(diǎn)間的相對位置關(guān)系，采用區(qū)間路由標(biāo)記法對圖中的節(jié)點(diǎn)進(jìn)行順序標(biāo)記。

1.1 標(biāo)記系統(tǒng)的建立

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

2)反饋?zhàn)訕浯笮?子樹大小是指以某節(jié)點(diǎn)為根的子樹中包含的節(jié)點(diǎn)數(shù)目，包括子樹根節(jié)點(diǎn)自身。該過程從葉節(jié)點(diǎn)開始，一直持續(xù)到根節(jié)點(diǎn)，最終使得根節(jié)點(diǎn)獲得整個(gè)樹的大小，而父節(jié)點(diǎn)獲得各個(gè)子節(jié)點(diǎn)子樹大小。

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

1.2 標(biāo)記性質(zhì)

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

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

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

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

定義3 RID：節(jié)點(diǎn)在SPT-1上的特征編號，能輔助數(shù)據(jù)路由。

2 LBEB算法設(shè)計(jì)

LBEB使用標(biāo)記系統(tǒng)完成數(shù)據(jù)路由，同時(shí)，為平衡路由效率、時(shí)延要求和網(wǎng)絡(luò)能耗， 對于不同類型的數(shù)據(jù)采用不同的路由策略：緊急數(shù)據(jù)使用貪婪策略；平常數(shù)據(jù)使用平衡策略。

2.1 貪婪策略

依據(jù)1.1節(jié)區(qū)間標(biāo)記的分配原則，不同節(jié)點(diǎn)S,D間的標(biāo)記距離可定義如下

LD(i)，LS(i)分別表示D和S第i段有覆蓋關(guān)系的標(biāo)記區(qū)間的長度；ND(i)，NS(i)分別表示D和S在SPT-i上的特征編號，m為根節(jié)點(diǎn)數(shù)。

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

2.2 平衡策略

平衡策略需要綜合考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)與目的節(jié)點(diǎn)的標(biāo)記距離、剩余能量以及未來一段時(shí)間內(nèi)的負(fù)載情況，然后在此基礎(chǔ)之上從距離目的節(jié)點(diǎn)更近的可選鄰居節(jié)點(diǎn)集或候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集中選擇能量負(fù)載比最高者作為下一跳節(jié)點(diǎn)。

記Nb為節(jié)點(diǎn)的鄰居集，Sc為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，c為候選系數(shù)，三者間的關(guān)系如下：

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

Sc的構(gòu)造原則如下：1)包含關(guān)系優(yōu)先；2)同優(yōu)先級中，與目的節(jié)點(diǎn)標(biāo)記距離小者優(yōu)先；3)到目的節(jié)點(diǎn)的標(biāo)記距離小于當(dāng)前節(jié)點(diǎn)；4)若Sc為空，選擇SP-1進(jìn)行上溯，直到當(dāng)前節(jié)點(diǎn)或其鄰居節(jié)點(diǎn)包含目的節(jié)點(diǎn)或被目的節(jié)點(diǎn)包含。

同時(shí)，為估計(jì)未來一段時(shí)間Tw內(nèi)節(jié)點(diǎn)的負(fù)載情況，節(jié)點(diǎn)需記錄上一個(gè)Tw內(nèi)的負(fù)載，然后利用指數(shù)加權(quán)移動(dòng)平均法進(jìn)行預(yù)估

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

其中，Qk-1和Q(k-1)分別表示第k-1個(gè)Tw時(shí)段內(nèi)節(jié)點(diǎn)負(fù)載的估計(jì)值和觀察值，而a為加權(quán)系數(shù)，決定預(yù)估計(jì)算法中最近一次觀察值的權(quán)重。記節(jié)點(diǎn)當(dāng)前剩余能量為E，那么節(jié)點(diǎn)在第k個(gè)Tw內(nèi)的能量負(fù)載比R(k)=E/Qk。R(k)的值通過周期性(周期為Tw)報(bào)文廣播通知鄰居節(jié)點(diǎn)，作為平衡策略從候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集Sc中選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的依據(jù)(選擇其中R(k)值最高的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn))。

3 仿真分析

使用OMNET++對LBEB進(jìn)行仿真，主要參數(shù)：部署區(qū)域?yàn)?00 m×300 m；通信半徑為30 m；平均鄰居數(shù)為15；候選系數(shù)c和加權(quán)系數(shù)a分別為0.6和0.5；節(jié)點(diǎn)初始能量為1 000個(gè)單位，發(fā)送一個(gè)緊急數(shù)據(jù)包和一個(gè)平常數(shù)據(jù)包分別消耗1個(gè)和4個(gè)能量單位。接收狀態(tài)能耗與空閑偵聽類似，忽略不計(jì)。

3.1 路由效率對比消息開銷

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

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

3.2 緊急數(shù)據(jù)包的端到端延遲

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

圖2 緊急數(shù)據(jù)包的端到端延遲

3.3 網(wǎng)絡(luò)生命期

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

圖3 網(wǎng)絡(luò)生命期比較

4 結(jié)束語

本文提出LBEB算法用以解決WSNs中數(shù)據(jù)的高效傳輸與網(wǎng)絡(luò)生命期的最大化。首先，應(yīng)用圖嵌入式技術(shù)在網(wǎng)絡(luò)中嵌入多棵獨(dú)立最短路徑樹，并由此構(gòu)建起一個(gè)不依賴節(jié)點(diǎn)物理位置的虛擬標(biāo)記系統(tǒng)；然后，基于此標(biāo)記系統(tǒng)設(shè)計(jì)了針對不同數(shù)據(jù)類型的轉(zhuǎn)發(fā)策略，在滿足數(shù)據(jù)時(shí)延要求的同時(shí)均衡節(jié)點(diǎn)負(fù)載和能耗，從而實(shí)現(xiàn)數(shù)據(jù)的高效傳輸與網(wǎng)絡(luò)生命期的最大化；最后，通過路由效率對比消息開銷、緊

急數(shù)據(jù)包的端到端延遲以及網(wǎng)絡(luò)生命期3個(gè)仿真實(shí)驗(yàn)驗(yàn)證了LBEB算法的有效性；不過，LBEB算法只適用于靜態(tài)網(wǎng)絡(luò)或弱動(dòng)態(tài)網(wǎng)絡(luò)，加入動(dòng)態(tài)性支持是進(jìn)一步研究的一個(gè)方向，即節(jié)點(diǎn)失效或新節(jié)點(diǎn)加入后如何平穩(wěn)、快速地對標(biāo)記系統(tǒng)加以調(diào)整。

參考文獻(xiàn):

[1] 蔚趙春,周水庚,關(guān)佶紅.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)存儲與訪問研究進(jìn)展[J].電子學(xué)報(bào),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] 陳 衡,錢德沛,伍衛(wèi)國.傳感器網(wǎng)絡(luò)基于鄰居信息量化的能量平衡路由[J].西安交通大學(xué)學(xué)報(bào),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] 李志剛,陳衛(wèi)衛(wèi),肖 儂,等.無線傳感器網(wǎng)絡(luò)中基于網(wǎng)絡(luò)嵌入的弱貪婪路由協(xié)議[J].通信學(xué)報(bào),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] 梁慶偉,姚道遠(yuǎn),鞏思亮.一種保障時(shí)延能量高效的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].西安交通大學(xué)學(xué)報(bào),2012,46(6):48-53.