一種高能效傳感網(wǎng)路由控制算法*

張秋霞， 何留杰

(黃河科技學(xué)院 現(xiàn)代教育技術(shù)中心， 鄭州 450063)

無線傳感器網(wǎng)絡(luò)WSNs[1]通過部署在監(jiān)測區(qū)域中的傳感器節(jié)點，對監(jiān)測對象協(xié)作感知、采集并處理其信息，然后發(fā)送到基站BS.WSNs技術(shù)以物物相聯(lián)的觀念改變了人類社會與大自然的交流方式，它對信息世界與客觀物理世界進行了邏輯融合，被廣泛應(yīng)用于社會各個領(lǐng)域，包括環(huán)境監(jiān)測、工業(yè)控制、智能家居、軍工航天和城市交通等，形成了以其作為支撐的泛在物聯(lián)網(wǎng)絡(luò).無線傳感器網(wǎng)絡(luò)路由包括平面路由和分層結(jié)構(gòu).平面路由中傳感器節(jié)點身份對等，網(wǎng)絡(luò)流量相對均勻，但適用的網(wǎng)絡(luò)規(guī)模相對較小.分層路由采用簇對傳感器節(jié)點進行管理，由成簇、簇維護、簇內(nèi)路由三個階段組成.成簇負(fù)責(zé)動態(tài)環(huán)境下的傳感器節(jié)點聚集成簇問題，簇維護負(fù)責(zé)節(jié)點移動與節(jié)點進出網(wǎng)絡(luò)中的結(jié)構(gòu)維護，簇內(nèi)路由負(fù)責(zé)局部范圍的數(shù)據(jù)通信.

早期的WSNs多采用均勻分簇的分層路由，即以某種標(biāo)準(zhǔn)將網(wǎng)絡(luò)劃分為規(guī)模均等的簇.LEACH[2]是無線傳感器網(wǎng)絡(luò)最早的分簇路由，該協(xié)議隨機選取簇頭，非簇頭節(jié)點將數(shù)據(jù)傳送到簇頭，簇頭進行數(shù)據(jù)融合后發(fā)送到基站.LEACH減少了與基站直接通信的節(jié)點數(shù)和數(shù)據(jù)量，且采用了簇頭輪換機制，有較好的節(jié)能效果.TEEN[3]對LEACH做了改進，通過設(shè)置廣播硬門限值和軟門限值降低了不必要的數(shù)據(jù)傳輸次數(shù)，使數(shù)據(jù)傳輸更加高效.PEGASIS[4]在LEACH的基礎(chǔ)上加入了鏈?zhǔn)浇Y(jié)構(gòu)，即各節(jié)點均從鄰居接收數(shù)據(jù)，并向另一鄰居發(fā)送數(shù)據(jù)，最終發(fā)送給基站.PEGASIS的通信只限于鄰居節(jié)點，每輪只隨機選取一個簇頭與基站通信，大大減少了通信量.

可見，均勻分簇?zé)o論簇間路由的形式是單跳還是多跳，均會導(dǎo)致各個簇的能耗不均衡，個別簇頭和簇成員會快速死亡，而非均勻分簇可有效改善該問題.在EECS協(xié)議[5]中，節(jié)點兼顧考慮簇頭到BS的距離以及自身到簇頭的距離，以便建立規(guī)模不均勻的簇結(jié)構(gòu).由于采用了與LEACH一樣的簇間單跳模式，EECS使得距離BS更遠(yuǎn)的簇規(guī)模更小，但這僅緩解了簇頭的能耗不均，整個網(wǎng)絡(luò)的能耗均衡問題仍未得到解決.NUCRP[6-7]以非均勻分簇方式平衡簇頭能耗，考慮了簇內(nèi)通信和簇間通信能耗，前者能耗與簇內(nèi)成員數(shù)量有關(guān)，后者能耗則是轉(zhuǎn)發(fā)數(shù)據(jù)量的函數(shù).EEUC[8]為了使得靠近BS的簇規(guī)模更小，設(shè)置了非均勻的簇頭競爭半徑，使簇頭能夠節(jié)約部分能耗.此外，選擇中繼節(jié)點時，不僅考慮了候選中繼與BS的位置關(guān)系，還考慮節(jié)點能量，從而進一步均衡能耗.AC-EBUC[9]在EEUC的基礎(chǔ)上對簇頭的隨機周期性簇首選擇方式做了改進，即首輪所有節(jié)點參與競選，而后續(xù)輪簇內(nèi)再進行調(diào)整.文獻[10-11]將單跳改進為多跳方式，由簇頭承擔(dān)鄰居簇頭的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，解決了簇頭的能耗問題，并改進了簇頭的選擇策略.EBFA[12]采用非均勻分簇和簇間多跳轉(zhuǎn)發(fā)策略，在多跳轉(zhuǎn)發(fā)階段，引入社會福利函數(shù)評估數(shù)據(jù)轉(zhuǎn)發(fā)路徑上節(jié)點間的能量均衡程度，選擇能量均衡程度較好的作為轉(zhuǎn)發(fā)節(jié)點.

本文提出一種新的高能效分簇路由，新路由能夠通過非均勻規(guī)模的分簇與簇間多跳路由方式有效延長網(wǎng)絡(luò)存活時間.引入簇頭競爭算法有效地選擇簇頭，選擇標(biāo)準(zhǔn)同時考慮了候選簇頭的剩余能量和鄰居的剩余能量，目的是使距離BS更近的候選簇頭在競爭正式簇頭時范圍更小，這樣導(dǎo)致距離基站較近的簇具有更小的規(guī)模，簇成員也更少，簇內(nèi)通信時產(chǎn)生的能耗也更少，直接有利于作為中繼節(jié)點的簇頭可以承擔(dān)后面的轉(zhuǎn)發(fā)任務(wù)，最終帶來更加均衡的能耗水平.

1 UCER協(xié)議設(shè)計

1.1 網(wǎng)絡(luò)模型與節(jié)點能量模型

對本文考慮的無線傳感器網(wǎng)絡(luò)屬性做如下假設(shè)：1)觀測區(qū)域為矩形區(qū)域，所有節(jié)點不具備移動性；2)節(jié)點是同質(zhì)的，具有唯一的標(biāo)識，且具備數(shù)據(jù)融合功能；3)節(jié)點可以根據(jù)距離對發(fā)射功率進行調(diào)整；4)收發(fā)雙方的通信鏈路具有對稱性.

網(wǎng)絡(luò)節(jié)點能耗采用文獻[13]中提出的無線通信能耗模型，如圖1所示.模型由功率放大器和射頻電路組成，前者能耗根據(jù)收發(fā)節(jié)點間距離的不同分為自由空間模型和多路徑衰減模型.自由空間模型的路徑損耗指數(shù)為2(d2功耗)，多路徑衰減模型的路徑損耗指數(shù)為4(d4功耗).使用哪種模型取決于通信距離，若通信距離小于門限值，則使用自由空間模型.

圖1 節(jié)點能耗模型Fig.1 Model for energy consumption of nodes

根據(jù)文獻[13]中的能耗模型，若發(fā)送方發(fā)送lbit數(shù)據(jù)至距離d處，則其能耗為

ETx(l，d)=ETx-elec(l)+ETx-amp(l，d)

(1)

(2)

而接收lbit的消息時，接收方能耗為

ERx(l)=ERx-elec(l)=lEelec

(3)

為了簡化實驗過程，假設(shè)通信能耗采用Friss自由空間模型，簇j內(nèi)的成員節(jié)點數(shù)量為m，那么簇內(nèi)成員節(jié)點h發(fā)送lbit數(shù)據(jù)至簇頭j時的能耗為

(4)

式中，dhj為成員節(jié)點h與簇頭j之間的距離.

簇頭j消耗的總能量應(yīng)包括：接收簇內(nèi)所有成員節(jié)點發(fā)送數(shù)據(jù)的能耗、發(fā)送融合后數(shù)據(jù)的能耗以及接收和轉(zhuǎn)發(fā)其他K個簇頭數(shù)據(jù)的能耗，假設(shè)所有簇內(nèi)成員節(jié)點是近似的，則有

Ei= (K+1)m(ETx(l，d)+ERx(l))=

(K+1)ml(2Eelec+εfriss-ampd2)

(5)

結(jié)合式(4)、(5)可以看出，簇頭能耗由簇內(nèi)節(jié)點數(shù)m、需要轉(zhuǎn)發(fā)的數(shù)據(jù)量l、簇內(nèi)節(jié)點與簇頭間的距離dhj以及至下一跳中繼節(jié)點的距離d決定，因此，優(yōu)化這些參數(shù)將直接可以降低簇頭能耗，這也是本文選擇優(yōu)化簇頭選擇策略以及優(yōu)化數(shù)據(jù)傳輸路徑中中繼節(jié)點選擇的依據(jù)所在.

1.2 節(jié)點層次劃分

設(shè)矩形觀測區(qū)域中的網(wǎng)絡(luò)以基站BS為中心劃分為N個扇形區(qū)域，扇形區(qū)域的上邊界表示為UL，下邊界表示為LL，最遠(yuǎn)層次表示的非規(guī)則區(qū)域間距(上邊界與矩形下邊)設(shè)置為R0，該層次為不規(guī)則區(qū)域.計算層次UL邊和LL邊與BS間的距離，然后將該距離通過Hello廣播至全網(wǎng)，廣播消息格式為：網(wǎng)絡(luò)層數(shù)，UL邊與BS間距，LL邊與BS間距.同時，在部署階段，節(jié)點根據(jù)Hello廣播信號強度計算與BS的間距，同時節(jié)點通過該距離計算出自己所屬的層數(shù)i，其計算公式為

(6)

式中：Uj為UL邊的節(jié)點j與BS的間距；Uj′為LL邊的節(jié)點j′與BS的間距.節(jié)點計算層次的過程如算法1所示，節(jié)點層次劃分如圖2所示.

算法1計算節(jié)點層次

1) BS廣播Hello消息至觀測區(qū)域

2) For每個傳感節(jié)點

3) 節(jié)點Si接收Hello消息

4) End For

5) 計算節(jié)點Si與BS間的距離di_to_BS

6) Fori=1 ton-1

7) 如果LLi

8)Si.level=i

9) 否則

10)Si.level=n

11) End

12) End For

算法說明：步驟1)表明基站BS向全網(wǎng)廣播Hello消息，步驟2)～4)表明觀測區(qū)域的傳感節(jié)點接收步驟1)的Hello廣播，之后所有接收消息的傳感節(jié)點根據(jù)接收信號強度計算自身與BS之間的距離(步驟5))，步驟6)～12)則對所有節(jié)點進行層次劃分.

圖2 節(jié)點層次劃分Fig.2 Level division of nodes

1.3 簇頭選擇與成簇

節(jié)點接收Hello廣播后，需要將自身剩余能量及與BS距離發(fā)送至BS，基站根據(jù)該消息計算層次平均能量.在每輪的建簇階段，BS向全網(wǎng)廣播AvE_lay_msg消息(包含層次平均能量)，節(jié)點接收并進行閾值比較，因此，考慮節(jié)點剩余能量，本文改進閾值公式，將其定義為

(7)

算法2簇頭選擇與成簇過程

1) BS廣播消息AvE_lay_msg(AvE1，AvE2，…，AvEn)

2) 每個節(jié)點接收消息AvE_lay_msg

3) 設(shè)置隨機數(shù)u←Rand(0，1)

4) 計算Tthresh=PEr/Eave

5) 如果u

6) 設(shè)置節(jié)點狀態(tài)為candidate cluster_head

7) End

8) 如果節(jié)點狀態(tài)為candidate cluster_head

9) 節(jié)點廣播消息Compete_head_msg(ID，Er，R)

10) 否則

11) 退出

12) End

13) 當(dāng)candidate headSi接收來自Sj的Compete_head_msg時

14) 如果di_to_j

15) 添加Sj至集合Si.neighbor_head中

16) End

17) 當(dāng)節(jié)點狀態(tài)為candidate cluster_head時

18) 如果Sj∈Si.neighbor_head且Esi>Esj

19) 節(jié)點Si廣播消息Norm_head_msg(ID)并退出

20) 否則如果Esi=Esj

21) 如果di≤dj

22) 節(jié)點Si廣播消息Norm_head_msg(ID)并退出

23) End

24) End

25) 當(dāng)節(jié)點Sj接收來自Sj的消息Norm_head_msg時

26) 如果Sj∈Si.neighbor_head

27) 節(jié)點Sj廣播消息Exit_head_msg(ID)并退出

28) End

29) 當(dāng)節(jié)點狀態(tài)為normal cluster_head

30) 節(jié)點廣播消息CH_ADV_msg(ID)

31) 如果節(jié)點狀態(tài)為common

32) 節(jié)點接收CH_ADV_msg并廣播Join_ADV_msg(ID)

33) End

其中：P∈[0，1]為任一節(jié)點當(dāng)選簇頭的概率；Tthresh為單個節(jié)點成為候選簇頭的概率；Er為節(jié)點剩余能量；Eave為層次平均能量；R為簇頭競選半徑；Si.neighbor_head為候選簇頭的鄰居候選簇頭集.表1為主要的消息定義.鄰居簇頭集合定義Si.neighbor_head={Sj|Sj為候選簇頭，di_to_j

表1 消息說明Tab.1 Message description

算法說明：步驟1)中BS廣播消息AvE_lay_msg(包含層次平均能量)至全網(wǎng)，步驟2)表明各網(wǎng)絡(luò)節(jié)點接收了該消息；步驟3)～7)表示候選簇頭選擇策略，步驟4)中的閾值Tthresh考慮了節(jié)點層次平均能量和自身剩余能量；步驟8)～12)表明，對于候選簇頭，需要廣播正式簇頭競選消息Compete_head_msg，其他節(jié)點則進入休眠；步驟13)～16)表示，若兩個候選簇頭處于兩者中競選半徑較大的范圍內(nèi)，需要根據(jù)廣播消息構(gòu)建鄰居候選簇頭集Si.neighbor_head，并在構(gòu)建完之后，通過步驟17)～24)選出最終簇頭，即鄰居候選簇頭中剩余能量最大的當(dāng)選簇頭，并廣播正式簇頭消息Norm_head_msg；步驟25)～28)表明正式簇頭廣播當(dāng)選消息，而其鄰居候選簇頭集中的簇頭廣播消息Exit_head_msg退出競爭，消息中包含節(jié)點標(biāo)識符；步驟29)～33)表明簇頭向全網(wǎng)廣播簇頭消息CH_ADV_msg，而其他節(jié)點廣播加入消息Join_ADV_msg進行入簇.

在本文設(shè)計的簇頭選擇與成簇算法中，對各層次的候選簇頭競爭半徑重新進行了定義，以形成非均勻簇.算法目標(biāo)是使得靠近BS的簇內(nèi)成員更少，因此，靠近BS的候選簇頭競爭半徑應(yīng)較小.設(shè)簇頭競爭半徑為

(8)

式中：k為節(jié)點所處的層次；n為網(wǎng)絡(luò)劃分的層數(shù)；c為[0，1]之間的常數(shù).

1.4 簇間路由

單跳通信方式會使得距離BS較遠(yuǎn)的簇頭較快死亡，影響網(wǎng)絡(luò)的連通性.UCER協(xié)議采用多跳的簇間路由方式將各簇頭數(shù)據(jù)轉(zhuǎn)發(fā)至BS.本文假設(shè)不同簇間傳送的數(shù)據(jù)無法在單個節(jié)點上進一步進行數(shù)據(jù)融合，即所選擇的中繼簇頭節(jié)點只負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，模型如圖3所示.

圖3 多跳非均勻分簇Fig.3 Multi-hop unequal clustering

UCER令中繼路由節(jié)點的選取范圍為上層區(qū)域的簇頭中，即k層簇頭選擇k-i的簇頭作為中繼.簇頭Si選擇簇頭Sj作為中繼的條件為：1)Sj所在層次比Si所在層次離BS更近，即dj_to_BS

Si需要從候選中繼節(jié)點集中選擇數(shù)據(jù)路由中繼，在這個過程中，若只考慮節(jié)點剩余能量因素可能導(dǎo)致網(wǎng)絡(luò)整體能效下降.假設(shè)Si選擇Sj作為中繼，若采用Friss自由空間模型，設(shè)Sj接收數(shù)據(jù)后直接發(fā)送至BS，則能耗為

E2-hop=ETx(l，d(Si，Sj))+ERx(l)+

ETx(l，d(Sj，BS))=

l(Eelec+εfriss-ampd2(Si，Sj))+lEelec+

l(Eelec+εfriss-ampd2(Sj，BS))=

3lEelec+l2εfriss-amp(d2(Si，Sj)+

d2(Sj，BS))

(9)

由式(9)可知，總能耗E2-hop將取決于d2(Si，Sj)+d2(Sj，BS)，即節(jié)點Si與節(jié)點Sj之間的距離以及節(jié)點Sj與基站之間的距離.那么，如果Sj位于Si與基站之間，則此時能耗是最小的.為了兼顧考慮傳感器節(jié)點的剩余能量以及通信鏈路能量開銷，中繼節(jié)點選擇策略為：Si從所有候選中繼節(jié)點能耗最小的兩個節(jié)點中進行選擇，剩余能量更高的節(jié)點作為正式中繼節(jié)點，因此，本文定義中繼簇頭節(jié)點的轉(zhuǎn)發(fā)參數(shù)為

(10)

式中：Einitial為節(jié)點的初始能量；α和β為權(quán)重因子.當(dāng)選擇的中繼節(jié)點Tc(j)值較小時，表明該中繼節(jié)點不僅可以節(jié)省能耗，還可以均衡該節(jié)點作為中繼節(jié)點在通信鏈路上的負(fù)載.在此過程中，需要建立一個鄰居簇頭信息表，如表2所示.

表2 鄰居簇頭信息Tab.2 Information of neighbor cluster heads

中繼節(jié)點選擇過程如算法3所示.

算法3中繼節(jié)點選擇過程

1) For網(wǎng)絡(luò)中的每個簇頭

2) 如果dj_to_BS

3) 添加Sj至集合Si.relay

4) End

5) End For

6) 如果Si.relay為空集

7)Si.nexthop=BS

8) 否則

9)Si.nexthop=MAX(Em，En)

10)Em(2-hop)，En(2-hop)

11) End

算法說明：在選擇中繼節(jié)點過程中，簇頭維護一個集合Si.relay，用來存儲候選中繼節(jié)點中符合以上三個條件的可能中繼節(jié)點；步驟6)～7)表明，如果Si.relay中沒有符合條件的中繼節(jié)點，Si則選擇直接將數(shù)據(jù)發(fā)送至基站BS；否則，通過步 驟8)～11)，Si選擇剩余能量更高的作為通向基站的中繼節(jié)點.

2 仿真實驗

2.1 實驗配置

本文利用NS2對協(xié)議進行了實驗分析.實驗中節(jié)點的部署位置由NS2的genscen工具隨機生成，選取均勻分簇路由協(xié)議LEACH、非均勻分簇路由協(xié)議EEUC和AC-UBEC作為比較協(xié)議.實驗參數(shù)如表3所示.

表3 實驗參數(shù)設(shè)置Tab.3 Setting of experimental parameters

選取以下五個性能標(biāo)準(zhǔn)進行觀察與比較：成簇量、簇頭分布、簇頭能耗、建簇能耗、節(jié)點存活量.其中，簇頭分布以簇頭間距表示，建簇能耗主要來源于成簇時的消息傳播.

2.2 實驗結(jié)果與分析

圖4為新協(xié)議的成簇個數(shù)分布.LEACH的成簇量分布范圍最大，而EEUC和UCER相比較更為集中，主要原因是三種協(xié)議在簇頭選擇上的差異.LEACH的簇頭選擇由隨機數(shù)控制，每一輪的成簇量是無法控制的.相比較而言，EEUC和UCER通過競爭方式產(chǎn)生簇頭，每一輪產(chǎn)生的成簇量則更為穩(wěn)定.同時，UCER在層次內(nèi)以計時廣播形式和設(shè)置成簇半徑方式取代競爭協(xié)商，簇頭數(shù)量更為穩(wěn)定.

圖4 新協(xié)議的成簇個數(shù)分布Fig.4 Number distribution of clusters of new protocols

圖5為幾種協(xié)議所產(chǎn)生的簇頭間距變化.可以看出，LEACH中簇頭間距平均約為20 m，EEUC約為40 m，本文協(xié)議UCER約為65 m.該指標(biāo)直接受成簇數(shù)量的影響，在固定區(qū)域內(nèi)，成簇量過多，則直接導(dǎo)致簇頭間距過小，LEACH可能導(dǎo)致在局部區(qū)域內(nèi)簇頭過于密集，而其他區(qū)域簇頭過于稀少，直接導(dǎo)致簇內(nèi)數(shù)據(jù)通信產(chǎn)生更大的開銷.而UCER通過在層次內(nèi)部設(shè)置競爭半徑使得各簇頭不在相互競爭半徑內(nèi)，簇頭分布更加均勻.

圖5 簇頭間的最小距離Fig.5 Minimal distance between cluster heads

圖6為協(xié)議的簇頭能耗變化.簇頭能耗的變化取決于協(xié)議在簇間是單跳還是多跳方式.由于LEACH與基站的數(shù)據(jù)通信是單跳方式，簇頭能耗最大，因為長距離通信占據(jù)能耗主要部分.EEUC和UCER采用簇間多跳方式路由，但EEUC每一輪的簇頭選擇是在全網(wǎng)范圍內(nèi)進行廣播競爭，消耗了更多的能耗.UCER則在層次內(nèi)進行廣播簇頭選擇，節(jié)省了部分?jǐn)?shù)據(jù)通信能耗.同時，由于文中假設(shè)簇頭上的數(shù)據(jù)融合能耗是固定的，所以這部分能耗不會因單跳或多跳通信方式產(chǎn)生很大變化.

圖6 簇頭能耗Fig.6 Energy consumption of cluster heads

圖7為幾種協(xié)議的成簇能耗，表現(xiàn)為網(wǎng)絡(luò)的總剩余能量.由于EEUC和UCER在成簇階段加入了簇頭競爭機制，候選節(jié)點需要在局部范圍內(nèi)進行簇頭競選，此時需要廣播競選消息，但由于該消息報文容量極小，所以相較LEACH而言，會帶來一部分能耗.LEACH成簇是隨機的，沒有節(jié)點間的簇頭競爭，因此網(wǎng)絡(luò)剩余能量更多.總體來說，盡管成簇能耗變大，但所占比例較小，通過簇頭競爭的非均勻分簇路由效率仍是更好的.

圖7 建簇能耗Fig.7 Energy consumption of cluster forming

圖8為網(wǎng)絡(luò)的生存時間，以傳感器節(jié)點是否存活情況表示.可以看出，LEACH最早出現(xiàn)節(jié)點死亡情況，UCER則到40輪才出現(xiàn)第一個節(jié)點死亡.主要原因是新協(xié)議在選擇簇頭時考慮了節(jié)點的剩余能量和各層次的平均剩余能量，且根據(jù)距離基站的遠(yuǎn)近劃分將節(jié)點組織成不均勻大小的簇規(guī)模，并采用多跳的簇間路由方式，為節(jié)點節(jié)省了能耗.EEUC出現(xiàn)節(jié)點死亡和最后一個節(jié)點死亡均早于UCER，這是由于UCER中提出的計時廣播方式能有效減少簇頭競爭階段產(chǎn)生的通信能耗，而EEUC的全局協(xié)商簇頭選擇機制相對而言會消耗更多能耗，且UCER層次內(nèi)的簇頭選擇機制為節(jié)點進一步節(jié)省了能耗，其網(wǎng)絡(luò)生存時間更長.

圖8 存活節(jié)點數(shù)量Fig.8 Number of survival nodes

3 結(jié) 論

本文提出了一種基于層次的多跳非均勻分簇路由協(xié)議UCER.改進協(xié)議的主要工作是對簇頭選舉、簇間路由和成簇規(guī)模進行了改進，旨在讓具有更多能量的節(jié)點擔(dān)任簇頭，并基于層次的劃分形成非均勻簇結(jié)構(gòu)，以支持后續(xù)數(shù)據(jù)的簇間多跳路由.結(jié)果表明，UCER協(xié)議在簇頭分布的合理性與節(jié)省能耗方面均有更好表現(xiàn).