WSNs中一種能耗均衡的傳染路由

陳明明, 王 寧,3,陳 亮,陳育智

(1. 廈門(mén)華廈學(xué)院, 福建 廈門(mén) 361026；2. 新一代信息通信技術(shù)與智慧教育福建省高校工程研究中心, 福建 廈門(mén) 361026；3. 廈門(mén)大學(xué), 福建 廈門(mén) 361005；4. 昆明理工大學(xué),云南 昆明 650504)

0 引 言

無(wú)線(xiàn)傳感網(wǎng)絡(luò) (Wireless Sensor Networks，WSNs)[1-2]是由微型、低成本的傳感節(jié)點(diǎn)自組連通的網(wǎng)絡(luò)。每個(gè)傳感節(jié)點(diǎn)能夠感測(cè)、傳輸和接收數(shù)據(jù)。這些節(jié)點(diǎn)是由電池供電。當(dāng)節(jié)點(diǎn)電池耗盡，不便于補(bǔ)充能量。而一旦節(jié)點(diǎn)能量耗盡，節(jié)點(diǎn)就失效，并無(wú)法工作。因此，有效地利用節(jié)點(diǎn)能量成為WSNs的研究熱點(diǎn)之一。

而傳輸數(shù)據(jù)所消耗的能量占據(jù)節(jié)點(diǎn)的80%。因此，高效地完成數(shù)據(jù)傳輸策略能夠降低能耗[3]。傳感節(jié)點(diǎn)需要實(shí)時(shí)感測(cè)數(shù)據(jù)，再將數(shù)據(jù)傳輸至信宿。由于傳感節(jié)點(diǎn)失效，網(wǎng)絡(luò)連通率并不高，降低了數(shù)據(jù)包傳遞成功率，這給數(shù)據(jù)傳輸?shù)目煽啃蕴岢隽颂魬?zhàn)。

傳染路由(Gossip)是典型的容錯(cuò)路由[4]。當(dāng)傳感節(jié)點(diǎn)需要將數(shù)據(jù)傳輸至控制中心(信宿)，它就從鄰居節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)(轉(zhuǎn)發(fā)節(jié)點(diǎn))。然后，轉(zhuǎn)發(fā)節(jié)點(diǎn)再?gòu)乃泥従庸?jié)點(diǎn)中選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，直到信宿收到數(shù)據(jù)。信宿可能收到來(lái)自不同路徑的同一份數(shù)據(jù)多個(gè)復(fù)本。這增加了冗余。

此外，由于多個(gè)節(jié)點(diǎn)參與轉(zhuǎn)發(fā)/接收數(shù)據(jù)，消耗了大量的能量。因此，控制參與節(jié)點(diǎn)數(shù)是十分重要的?？赏ㄟ^(guò)優(yōu)先策略，只選擇部分節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。只允許部分節(jié)點(diǎn)傳輸數(shù)據(jù)，也減少數(shù)據(jù)在網(wǎng)絡(luò)中的復(fù)本數(shù)。最終，能夠減少能耗，提高網(wǎng)絡(luò)壽命。

目前，有基于概率、計(jì)數(shù)和距離產(chǎn)生轉(zhuǎn)發(fā)節(jié)點(diǎn)方案。其中概率方案最簡(jiǎn)單、易實(shí)施。節(jié)點(diǎn)以一定概率從鄰居節(jié)點(diǎn)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。而基于計(jì)數(shù)方案是依據(jù)離目的節(jié)點(diǎn)的跳數(shù)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)?；诰嚯x方案是通過(guò)依據(jù)節(jié)點(diǎn)位置信息選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。

實(shí)質(zhì)上，控制參與路由的節(jié)點(diǎn)數(shù)是降低Gossip路由能耗的關(guān)鍵。為此，提出基于能耗均衡的傳染路由(Energy Consumption Balance-Gossip, ECB-G)。ECB-G路由通過(guò)鄰居節(jié)點(diǎn)的位置和能量信息選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，減少參與數(shù)據(jù)包轉(zhuǎn)發(fā)的節(jié)點(diǎn)，進(jìn)而控制能耗。同時(shí)，依據(jù)節(jié)點(diǎn)的距離信息擇優(yōu)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而構(gòu)建穩(wěn)定的路由，減少重傳次數(shù)，提高帶寬利用率。仿真結(jié)果證實(shí)了ECB-G路由在能耗和帶寬利用率方面具有良好的性能。

1 系統(tǒng)模型

1.1 ECB-G路由概述

用連通圖G(V,E)表示W(wǎng)SN拓?fù)浣Y(jié)構(gòu)，其中V為頂點(diǎn)集，表示傳感節(jié)點(diǎn)。而E為邊集，表示節(jié)點(diǎn)間直接連通的鏈路。假定網(wǎng)絡(luò)有N個(gè)節(jié)點(diǎn)。令(xi,yi)表示第i個(gè)節(jié)點(diǎn)si的位置。

整個(gè)ECB-G路由由四個(gè)階段構(gòu)成，如圖1所示。首先，發(fā)送請(qǐng)求數(shù)據(jù)包，再計(jì)算距離，然后選擇最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)，最后轉(zhuǎn)發(fā)數(shù)據(jù)。

圖1 ECB-G路由框架

當(dāng)節(jié)點(diǎn)需要傳輸數(shù)據(jù)Data，就向鄰居節(jié)點(diǎn)發(fā)送請(qǐng)求數(shù)據(jù)包(Request Packet, RQP)，旨在收集鄰居節(jié)點(diǎn)的信息。一旦收到RQP，鄰居節(jié)點(diǎn)就回復(fù)數(shù)據(jù)包(Reply Packet, RPP)，其包含節(jié)點(diǎn)的剩余能量和位置信息。

再依據(jù)鄰居節(jié)點(diǎn)的能量和位置信息，計(jì)算節(jié)點(diǎn)成為轉(zhuǎn)發(fā)節(jié)點(diǎn)概率的分值。再選擇具有最高分值的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。最后，由轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。

1.2 能量模型

采用如圖2所示的能耗模型[5]。令Esd(m,d)表示傳輸m比特?cái)?shù)據(jù)、傳輸距離d時(shí)節(jié)點(diǎn)消耗的能量：

(1)

圖2 能量消耗模型

2 ECB-G路由

2.1 能效均衡因子

令E0表示節(jié)點(diǎn)的初始能量。假定所有節(jié)點(diǎn)具有相同初始能量。令Er(i)表示節(jié)點(diǎn)si的剩余能量。能效均衡因子考慮節(jié)點(diǎn)能量消耗速度以及其鄰居節(jié)點(diǎn)的平均剩余能量。

考慮平均剩余能量的原因在于：若節(jié)點(diǎn)自身具有高的剩余能量，但其鄰居節(jié)點(diǎn)的剩余能量低。這容易使節(jié)點(diǎn)處于“孤立無(wú)援”狀態(tài)，也無(wú)法將數(shù)據(jù)傳輸出去。

令ae(i)表示節(jié)點(diǎn)si的能效均衡因子，其定義如式(2)所示：

(2)

其中ni表示節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集，而|ni|表示集ni的節(jié)點(diǎn)數(shù)。sj表示節(jié)點(diǎn)si的一個(gè)鄰居節(jié)點(diǎn)，sj∈ni。

2.2 距離遠(yuǎn)近因子

再依據(jù)距離遠(yuǎn)近因子選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。具體而言，節(jié)點(diǎn)si需從其|ni|個(gè)鄰居節(jié)點(diǎn)中選擇具有距離最優(yōu)的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

令bd(i,j)表示節(jié)點(diǎn)si離節(jié)點(diǎn)sj的距離遠(yuǎn)近因子，其定義如式(3)所示：

(3)

其中di,j表示節(jié)點(diǎn)si離節(jié)點(diǎn)sj的歐式距離。而di,sink、dj,sink分別表示節(jié)點(diǎn)si離信宿sink、節(jié)點(diǎn)sj離信宿sink的歐式距離。如圖3所示。圖中的虛線(xiàn)圓圈表示節(jié)點(diǎn)si的通信范圍。節(jié)點(diǎn)sj為節(jié)點(diǎn)si的一個(gè)鄰居節(jié)點(diǎn)。

圖3 距離示意圖

2.3 數(shù)據(jù)轉(zhuǎn)發(fā)

當(dāng)節(jié)點(diǎn)si需要數(shù)據(jù)，就向鄰居節(jié)點(diǎn)發(fā)送RQP，其包含了自己位置。再監(jiān)聽(tīng)，并收集鄰居節(jié)點(diǎn)回復(fù)RRP包，進(jìn)而獲取鄰居節(jié)點(diǎn)的位置和能量信息。然后就廣播Datai。

鄰居節(jié)點(diǎn)(假定是節(jié)點(diǎn)sj)先依據(jù)分別式(2)、式(3)計(jì)算能效均衡因子和距離遠(yuǎn)近因子。再依據(jù)式(4)計(jì)算節(jié)點(diǎn)轉(zhuǎn)發(fā)分值。令Fj表示節(jié)點(diǎn)sj的轉(zhuǎn)發(fā)分值：

Fj=ae(i)+bd(i,j)

(4)

為了使具有最高分值的節(jié)點(diǎn)成為轉(zhuǎn)發(fā)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)(假定是節(jié)點(diǎn)sj)依據(jù)自己的分值設(shè)定定時(shí)器，且定時(shí)器的時(shí)長(zhǎng)與分值成反比。一旦定時(shí)完畢，且沒(méi)有監(jiān)聽(tīng)到其他節(jié)點(diǎn)轉(zhuǎn)發(fā)Datai，自己就立即轉(zhuǎn)發(fā)Datai。重復(fù)上述過(guò)程，直到數(shù)據(jù)包傳輸至信宿。整個(gè)流程如圖4所示。

圖4 數(shù)據(jù)轉(zhuǎn)發(fā)流程

3 性能仿真

3.1 仿真環(huán)境

利用NS2++軟件建立仿真平臺(tái)。傳感節(jié)點(diǎn)分布于80 m×60 m的矩形區(qū)域，信宿位于區(qū)域中心，且位置為(40,30)。節(jié)點(diǎn)傳輸范圍為20 m，所有節(jié)點(diǎn)的初始能量為0.5 J。具體的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

為了更好地分析ECB-G路由性能，選擇傳統(tǒng)的Gossip和文獻(xiàn)[6]提出的基于公平高效的位置Gossip路由(FEL-G)作為參照，并分析它們的傳輸時(shí)延、帶寬利用率、網(wǎng)絡(luò)壽命性能。其中，傳輸時(shí)延是指成功接收數(shù)據(jù)的平時(shí)時(shí)延。用式(5)計(jì)算帶寬利用率[7]：

λb=(Nme-Nre)/Nme

(5)

其中Nme表示所接收的數(shù)據(jù)包數(shù)。而Nre表示重傳的數(shù)據(jù)包數(shù)。

選擇每個(gè)節(jié)點(diǎn)失效的時(shí)間和最后一個(gè)節(jié)點(diǎn)失效時(shí)間評(píng)估網(wǎng)絡(luò)壽命[8]，且單位為輪(Round)。本文只考慮節(jié)點(diǎn)因能量消耗殆盡所導(dǎo)致的失效[9-10]，不考慮其他原因。

3.2 數(shù)據(jù)分析3.2.1 平均傳輸時(shí)延

首先分析數(shù)據(jù)傳輸時(shí)延隨節(jié)點(diǎn)數(shù)的變化情況。從圖5可知，數(shù)據(jù)傳輸時(shí)延隨節(jié)點(diǎn)數(shù)增加而上升。原因在于：數(shù)據(jù)傳輸時(shí)延隨網(wǎng)絡(luò)尺寸影響。節(jié)點(diǎn)數(shù)越多，導(dǎo)致的時(shí)延越長(zhǎng)。此外，傳統(tǒng)的Gossip路由的傳輸時(shí)延最低。這是主要是因?yàn)椋簜鹘y(tǒng)的Gossip路由在選擇下一跳節(jié)點(diǎn)時(shí)，并沒(méi)有進(jìn)行額外的計(jì)算，只是隨機(jī)地選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。而FEL-G路由和ECB-G路由是通過(guò)計(jì)算，選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，這增加了計(jì)算時(shí)延。

圖5 平均傳輸時(shí)延隨節(jié)點(diǎn)數(shù)的變化情況

3.2.2帶寬利用率

圖6顯示了三個(gè)路由協(xié)議的帶寬利用率。從圖6可知，相比于傳統(tǒng)的Gossip路由和FEL-G路由，提出的ECB-G路由的帶寬利用率得到提高。原因在于：ECB-G路由通過(guò)能耗均衡因子和距離遠(yuǎn)近因子選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，提高了路由的穩(wěn)定性，減少了重傳數(shù)據(jù)包次數(shù)。

圖6 帶寬利用率

3.2.3網(wǎng)絡(luò)壽命

圖7、8分別表示三個(gè)路由協(xié)議的第一個(gè)節(jié)點(diǎn)失效時(shí)間和最后一個(gè)節(jié)點(diǎn)失效時(shí)間。從圖6可知，傳統(tǒng)Gossip路由最早發(fā)生第一個(gè)節(jié)點(diǎn)失效，在整個(gè)節(jié)點(diǎn)變化的期間，它都是最先出現(xiàn)么一個(gè)失效節(jié)點(diǎn)。

圖7 第一個(gè)失效節(jié)點(diǎn)出現(xiàn)的時(shí)間

圖8 最后一個(gè)失效節(jié)點(diǎn)出現(xiàn)的時(shí)間

從圖8可知，提出的ECB-G路由的最后一個(gè)失效節(jié)點(diǎn)出現(xiàn)的時(shí)間最晚，性能優(yōu)于傳統(tǒng)Gossip路由和FEL-G路由。這充分說(shuō)明，ECB-G路由通過(guò)減少重傳次數(shù)、參與路由的節(jié)點(diǎn)，緩解了網(wǎng)絡(luò)能耗的速度。

4 結(jié) 語(yǔ)

針對(duì)Gossip路由的能耗問(wèn)題，提出能耗均衡的Gossip路由改進(jìn)路由ECB-G。ECB-G路由通過(guò)控制參與路由的節(jié)點(diǎn)數(shù)，減少能耗。利用鄰居節(jié)點(diǎn)的剩余能量和地理位置，選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，限定了轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)。仿真結(jié)果表明，相比于Gossip路由，提出的ECB-G路由有效地降低了能耗，并提高了帶寬利用率。