基于半徑遞增有向成簇的WSN路由算法

李長(zhǎng)庚，于澄澄，陳東海

（中南大學(xué)物理與電子學(xué)院，長(zhǎng)沙410083）

無(wú)線傳感器網(wǎng)絡(luò)［1］實(shí)現(xiàn)了計(jì)算機(jī)世界、自然世界與人類社會(huì)三元世界的無(wú)縫連接［2-4］，是一個(gè)全新的信息獲取平臺(tái)，其節(jié)點(diǎn)一般部署在無(wú)人值守地域，資源能量有限，因而在相關(guān)研究和設(shè)計(jì)時(shí)必須突出考慮能量因素，以獲得更長(zhǎng)的網(wǎng)絡(luò)生命周期。

分簇路由算法（如LEACH［5］）采用劃區(qū)組簇的方式，減小了與基站直接通信的節(jié)點(diǎn)數(shù)量，降低了通信開銷，其簇頭輪換機(jī)制能有效均衡簇頭的能耗消耗。其缺點(diǎn)在于簇頭地位關(guān)鍵，能量消耗大，容易出現(xiàn)“熱點(diǎn)”，簇頭選舉成本大，算法復(fù)雜度高，另外，簇規(guī)模與位置難以控制。

鏈?zhǔn)铰酚伤惴ǎㄈ鏟EGASIS［6］）通過(guò)減小節(jié)點(diǎn)間的平均通信距離，降低了網(wǎng)絡(luò)通信成本。其不足之處包括：一是鏈?zhǔn)浇Y(jié)構(gòu)層級(jí)眾多，通信延時(shí)較大；二是每個(gè)節(jié)點(diǎn)都承擔(dān)融合數(shù)據(jù)的任務(wù)，使得全網(wǎng)在數(shù)據(jù)融合方面的能量消耗偏大；三是由于采用貪婪算法尋找下一跳節(jié)點(diǎn)，在組網(wǎng)后期容易出現(xiàn)下一跳節(jié)點(diǎn)的距離較遠(yuǎn)的情況；四是鏈?zhǔn)浇Y(jié)構(gòu)不能對(duì)低能量節(jié)點(diǎn)進(jìn)入篩選，結(jié)構(gòu)中任何一個(gè)低能量節(jié)點(diǎn)的死亡都將導(dǎo)致結(jié)構(gòu)重組，增大了重組頻率。

LEACH算法是經(jīng)典的分簇路由算法，所有節(jié)點(diǎn)等概率地隨機(jī)擔(dān)當(dāng)簇頭，不考慮節(jié)點(diǎn)能量問(wèn)題。HEED［7］算法和TEEN［8］算法在選擇簇頭時(shí)考慮了能量因素，使得能量較大的節(jié)點(diǎn)擔(dān)任簇頭的概率較高。EEUC［9］算法、EOUCP［10］算法、CHTD算法、LDB?PL［11］算法引入了競(jìng)選半徑非均勻、競(jìng)選時(shí)間延遲、分層次成鏈等概念，文獻(xiàn)［12］還提出了代理簇頭的思想，這些算法改進(jìn)了選舉簇頭過(guò)程，其結(jié)果更趨合理，但依然存在一定的隨機(jī)性，且選舉過(guò)程受到多個(gè)約束條件限制，這增加了算法復(fù)雜度，同時(shí)提高了節(jié)點(diǎn)成簇組網(wǎng)過(guò)程的能耗。

基于以上分簇算法和鏈?zhǔn)剿惴▋?yōu)點(diǎn)與不足，設(shè)計(jì)一種半徑遞增有向成簇路由算法，其基本思想為“向基站方向成鏈，鏈中盡量成簇”，在操作程序上，各節(jié)點(diǎn)以較小半徑值R0組簇，然后簇頭和未進(jìn)入網(wǎng)絡(luò)的其他節(jié)點(diǎn)以更大的半徑2R0，在其前向傳輸區(qū)域內(nèi)選擇下一跳節(jié)點(diǎn)，之后再增大組網(wǎng)半徑，直至所有節(jié)點(diǎn)加入網(wǎng)絡(luò)。最后通過(guò)與LEACH算法和目前較典型的EEUC算法進(jìn)入仿真實(shí)驗(yàn)比較，驗(yàn)證算法性能并進(jìn)行參數(shù)分析。

1 系統(tǒng)模型與理論描述

1.1 網(wǎng)絡(luò)模型

無(wú)線傳感器網(wǎng)絡(luò)是一個(gè)面向應(yīng)用的系統(tǒng)，不同的應(yīng)用環(huán)境需要不同的網(wǎng)絡(luò)模型。假定N個(gè)傳感器節(jié)點(diǎn)隨機(jī)均勻分布在一個(gè)面積為M×M的區(qū)域A內(nèi)，并且有如下性質(zhì)：①所有節(jié)點(diǎn)部署后不移動(dòng)，能量不補(bǔ)充；②基站部署在區(qū)域A內(nèi)或邊界外一個(gè)固定位置，并且是唯一的；③無(wú)線信道滿足對(duì)稱性，即正向傳輸和反向傳輸?shù)攘康臄?shù)據(jù)消耗的能量相同；④節(jié)點(diǎn)同構(gòu)，具有相同的處理和通信能力，在網(wǎng)絡(luò)中地位平等；⑤節(jié)點(diǎn)無(wú)線發(fā)射功率可控，可根據(jù)距離調(diào)整發(fā)射功率；⑥節(jié)點(diǎn)可以獲取無(wú)線接收信號(hào)的強(qiáng)度［13］；⑦采用數(shù)據(jù)融合技術(shù)減少傳輸?shù)臄?shù)據(jù)量。

1.2 無(wú)線通信能量模型

網(wǎng)絡(luò)中節(jié)點(diǎn)通信采用Heinzelman等人在文獻(xiàn)［14，15］中提出的無(wú)線通信模型。當(dāng)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的距離小于閾值d0時(shí)，采用自由空間模型，否則采用多路衰減模型［16.17］。發(fā)送方發(fā)送長(zhǎng)度為lbit的數(shù)據(jù)到距離為d的位置消耗的能量為：

而接收方接收l(shuí)bit的數(shù)據(jù)所需能量為

其中，發(fā)射電路系數(shù)與接收電路系數(shù)數(shù)值相等，ETx-elec=ERx-elec=Eelec=50 nJ/bit，自由空間模型發(fā)射放大器εfs=10 pJ/bit/m2，多徑衰減模型發(fā)射放大器εmp=0.0013 pJ/bit/m4，數(shù)據(jù)融EDA=5 nJ/（bit/signal），閾值。

1.3 前向傳輸概念

在分簇結(jié)構(gòu)中，簇內(nèi)和簇間時(shí)常會(huì)出現(xiàn)某節(jié)點(diǎn)距離基站的距離比其下一跳節(jié)點(diǎn)距離基站更近的情況，即數(shù)據(jù)傳送到了距離基站更遠(yuǎn)的節(jié)點(diǎn)，為避免這種數(shù)據(jù)“回流”現(xiàn)象，這里引入前向傳輸?shù)母拍?。如圖1，節(jié)點(diǎn)i只把數(shù)據(jù)傳輸給在其通信范圍內(nèi)距離基站更近的鄰節(jié)點(diǎn)中的一個(gè)，其可能位置為：以基站為中心、dtoBS(i)為半徑的圓和以節(jié)點(diǎn)i為中心、以節(jié)點(diǎn)i通信距離參數(shù)dR為半徑的圓的重合區(qū)域，這排除了節(jié)點(diǎn)向后傳輸數(shù)據(jù)的可能。

圖1 前向傳輸區(qū)域示意圖

在前向傳輸區(qū)域內(nèi)選擇一個(gè)最終的節(jié)點(diǎn)作為節(jié)點(diǎn)的下一跳節(jié)點(diǎn)，引入節(jié)點(diǎn)度、剩余能量、節(jié)點(diǎn)間距、節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離等參數(shù)，構(gòu)建節(jié)點(diǎn)i到節(jié)點(diǎn)j的通信鏈路的前向傳輸因子FTF(ij)（Forward Transmission Factor）：

其中，Dback(j)為節(jié)點(diǎn)j的反向節(jié)點(diǎn)度（即由其節(jié)點(diǎn)度減去其可能的下一跳節(jié)點(diǎn)個(gè)數(shù)），E(j)為節(jié)點(diǎn)j當(dāng)前的剩余能量，dtoBS(i)和dtoBS(j)為節(jié)點(diǎn)i和節(jié)點(diǎn)j到基站的距離，d(i,j)為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離。

1.4 鏈中成簇思想

如圖2（a）所示，鏈?zhǔn)浇Y(jié)構(gòu)層級(jí)眾多，導(dǎo)致時(shí)延較大，同時(shí)，每個(gè)節(jié)點(diǎn)都承擔(dān)有融合數(shù)據(jù)的任務(wù)，造成額外能量消耗，再者，鏈?zhǔn)浇Y(jié)構(gòu)無(wú)法考慮能量因素，低能量節(jié)點(diǎn)也進(jìn)入鏈中，一旦某個(gè)節(jié)點(diǎn)過(guò)早消亡，鏈路即遭到破壞。圖2（b）和圖2（c）為不同能量條件下鏈中盡量成簇示意圖，即在鏈?zhǔn)浇Y(jié)構(gòu)基礎(chǔ)上，較為密集的節(jié)點(diǎn)或個(gè)別能量較低的節(jié)點(diǎn)，以簇的方式加入網(wǎng)絡(luò)。這種混合結(jié)構(gòu)保證了數(shù)據(jù)傳輸距離趨向最近，而傳輸層次也較少，且參與數(shù)據(jù)融合的節(jié)點(diǎn)也較少，最重要的是可以將低能量的節(jié)點(diǎn)以簇內(nèi)成員節(jié)點(diǎn)或者子節(jié)點(diǎn)的形式加入網(wǎng)絡(luò)，避免該節(jié)點(diǎn)進(jìn)入主路徑后由于過(guò)快消亡后導(dǎo)致大片區(qū)域數(shù)據(jù)丟失。

圖2 鏈中盡量成簇示意圖

1.5 平均剩余能量估計(jì)

為提高能量消耗均衡性，便于節(jié)點(diǎn)了解自身剩余能量在全網(wǎng)絡(luò)中所處的水平，通常需要對(duì)節(jié)點(diǎn)的平均能量進(jìn)行計(jì)算，但平均能量的計(jì)算需要統(tǒng)計(jì)全網(wǎng)的剩余能量信息，這對(duì)分布式路由算法是非常困難的，這里引入估計(jì)方法，對(duì)平均能量進(jìn)行相應(yīng)估計(jì)。首先粗略估計(jì)全網(wǎng)每一輪消耗的能量Eround

式（4）中，Etotal為全網(wǎng)初始總能量，r0為估計(jì)輪數(shù)，即網(wǎng)絡(luò)理論生存周期，在實(shí)驗(yàn)過(guò)程中可采用遞歸的方法取得，這里不作論述。估計(jì)全網(wǎng)剩余能量的平均值為

其中，N為節(jié)點(diǎn)數(shù)目，r為實(shí)驗(yàn)輪數(shù)。

2 半徑遞增有向成簇路由算法

根據(jù)本文算法的步驟，首先進(jìn)行初始化；然后在半徑R0內(nèi)組簇；然后若有節(jié)點(diǎn)尚未接入網(wǎng)絡(luò)則增加半徑，在新的半徑內(nèi)組簇；最后直至所有節(jié)點(diǎn)接入網(wǎng)絡(luò)，算法結(jié)束。

2.1 初始化

算法開始時(shí)，各節(jié)點(diǎn)自動(dòng)獲得一個(gè)唯一的節(jié)點(diǎn)ID，基站首先以額定的功率向全網(wǎng)廣播消息，節(jié)點(diǎn)根據(jù)接收消息的信號(hào)強(qiáng)度確定自身與基站的近似距離di-BS(i)［18］，并通過(guò)限定的功率與周圍節(jié)交換信息，分別確定半徑R0，2R0，3R0內(nèi)的節(jié)點(diǎn)度Ddegree1，Ddegree2，Ddegree3，反向節(jié)點(diǎn)度Dback1，Dback2，Dback3，并更新鄰節(jié)點(diǎn)信息表、緩存表等信息，如圖3所示。

2.2 半徑R0內(nèi)組簇

算法中，在半徑R0內(nèi)選擇簇頭和半徑2R0以上選擇下一跳節(jié)點(diǎn)時(shí)，引入了一個(gè)能量閾值，即要求節(jié)點(diǎn)能量必須大于，才有可能被選為簇頭或者下一跳節(jié)點(diǎn)。這里，為平均能量估計(jì)值，由式（4）～式（5）得到，w為調(diào)節(jié)參數(shù)，取值范圍為［0，1］。

圖3 隨機(jī)分布的傳感器節(jié)點(diǎn)

根據(jù)初始化數(shù)據(jù)，采用投票機(jī)制競(jìng)選簇頭。在未對(duì)全網(wǎng)節(jié)點(diǎn)劃分區(qū)域的情況下，各節(jié)點(diǎn)在包含自身在內(nèi)的半徑R0范圍內(nèi)，根據(jù)式（6）計(jì)算權(quán)值，將票投給權(quán)值最大的節(jié)點(diǎn)，使其成為備選簇頭，各備選簇頭統(tǒng)計(jì)自身被投票次數(shù)，并檢查半徑R0范圍內(nèi)有無(wú)其它備選簇頭，若有，則再次進(jìn)行權(quán)值比較，權(quán)值小的節(jié)點(diǎn)退出簇頭競(jìng)選，若無(wú)，則宣布自身成為簇頭，并召集簇內(nèi)成員。

其中，E(i)為節(jié)點(diǎn)剩余能量，為全網(wǎng)節(jié)點(diǎn)平均剩余能量，Ddegree1(i)為節(jié)點(diǎn)的節(jié)點(diǎn)度，w為調(diào)節(jié)系數(shù)。該權(quán)值綜合了節(jié)點(diǎn)能量和節(jié)點(diǎn)位置兩個(gè)因素，第一項(xiàng)反映了節(jié)點(diǎn)的能量因素，其對(duì)節(jié)點(diǎn)競(jìng)選簇頭設(shè)置了一個(gè)閾值，在達(dá)到這個(gè)閾值的條件下，節(jié)點(diǎn)能量越高，權(quán)值也會(huì)越大；式中第二項(xiàng)反映了節(jié)點(diǎn)的位置因素，即節(jié)點(diǎn)的節(jié)點(diǎn)度越大，其成為簇頭的權(quán)值也會(huì)越大。

如圖4，節(jié)點(diǎn)7和節(jié)點(diǎn)8在半徑R0范圍內(nèi)互為唯一鄰節(jié)點(diǎn)，在能量相同區(qū)別不大的情況下，由于節(jié)點(diǎn)8離基站更近，故而成為簇頭；又如節(jié)點(diǎn)6、節(jié)點(diǎn)9、節(jié)點(diǎn)10三個(gè)節(jié)點(diǎn)中，由于節(jié)點(diǎn)10的后向節(jié)點(diǎn)度大于節(jié)點(diǎn)6和節(jié)點(diǎn)9，更容易成為區(qū)域簇頭。

圖4 節(jié)點(diǎn)在半徑R0內(nèi)組簇示意圖

2.3 半徑2R0范圍內(nèi)組網(wǎng)

在半徑R0范圍內(nèi)完成組簇的路由結(jié)構(gòu)是不完整的，仍然存在較多的節(jié)點(diǎn)和簇頭未接入網(wǎng)絡(luò)，這些節(jié)點(diǎn)可以擴(kuò)大組簇半徑至2R0進(jìn)行組簇，其步驟和與前面相似。未接入網(wǎng)絡(luò)的節(jié)點(diǎn)i（或簇頭）查看半徑至2R0范圍內(nèi)鄰節(jié)點(diǎn)信息，若存在距離基站更近的鄰節(jié)點(diǎn)j（或簇頭），則根據(jù)根據(jù)公式（7）確定一個(gè)節(jié)點(diǎn)作為自身的簇頭并加入。

該權(quán)值計(jì)算式的前提是節(jié)點(diǎn)i必須位于節(jié)點(diǎn)j的前向傳輸區(qū)域內(nèi)（見(jiàn)圖1），即節(jié)點(diǎn)i必須位于以基站為中心、dtoBS(i)為半徑的圓和以節(jié)點(diǎn)i為中心、以通信距離參數(shù)dR=2R0為半徑的圓的重合區(qū)域，這排除了節(jié)點(diǎn)向后傳輸形成“回流”或“環(huán)路”的可能性。權(quán)值計(jì)算式的第一項(xiàng)為節(jié)點(diǎn)能量參考因素，它設(shè)置了一個(gè)閾值，即能量低于的節(jié)點(diǎn)不能成為備選節(jié)點(diǎn)；第二項(xiàng)為位置參考因素，它能保證更加靠近節(jié)點(diǎn)i和基站連線的節(jié)點(diǎn)具有更高的權(quán)值；第三項(xiàng)是基于盡量成簇思想（見(jiàn)圖2）的權(quán)重因子，它能保證反向節(jié)點(diǎn)度較大的節(jié)點(diǎn)同時(shí)接收更多的子節(jié)點(diǎn)，節(jié)省數(shù)據(jù)融合的成本，減少路由層次。圖5為節(jié)點(diǎn)在半徑2R0內(nèi)組簇示意圖。

圖5 節(jié)點(diǎn)在在半徑2R0內(nèi)組簇示意圖

針對(duì)仍未接入網(wǎng)絡(luò)的節(jié)點(diǎn)或者簇頭，繼續(xù)采取增加組簇半徑至3R0，4R0的方式，直至所有節(jié)點(diǎn)均接入網(wǎng)絡(luò)，構(gòu)成一個(gè)連通的簇樹。如圖6是半徑為3R0時(shí)的網(wǎng)絡(luò)圖，圖7為最終路由結(jié)構(gòu)。

圖6 節(jié)點(diǎn)在半徑3R0內(nèi)組簇示意圖

圖7 最終路由結(jié)構(gòu)圖

3 仿真實(shí)驗(yàn)與參數(shù)分析

3.1 仿真實(shí)驗(yàn)

仿真場(chǎng)景參數(shù)設(shè)置為：在邊長(zhǎng)M=100 m的區(qū)域內(nèi)隨機(jī)分布N=100個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)初始能量E=0.5 J，部署后不移動(dòng)，基站位于（150，50），其能量不受限制，初始成簇概率p=0.05，基準(zhǔn)半徑R0=22 m，假設(shè)節(jié)點(diǎn)每次發(fā)送或接收數(shù)據(jù)長(zhǎng)度為l=4 000 bits。在相同的條件下，對(duì)LEACH、EEUC和本案算法三者進(jìn)行比較，得到三種算法死亡節(jié)點(diǎn)個(gè)數(shù)隨仿真輪數(shù)的變化圖，見(jiàn)圖8。

圖8 N=100時(shí)生命周期比較圖

由圖8可以看出，LEACH算法在750輪左右開始出現(xiàn)死亡節(jié)點(diǎn)，到1350輪左右全部節(jié)點(diǎn)死亡，時(shí)間跨度約為600輪；EEUC算法在1200輪左右時(shí)節(jié)點(diǎn)開始死亡，在1600輪左右全部死亡，跨度約為400輪；本案算法在1500輪左右出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，到1800輪左右節(jié)點(diǎn)全部死亡，時(shí)間跨度約為300輪。這說(shuō)明新算法在能夠保證各節(jié)點(diǎn)的能量消耗速度更加平衡，即有能耗均衡性能上有較大提高。能量均衡性能提高帶來(lái)的直接結(jié)果是網(wǎng)絡(luò)生命周期的延長(zhǎng)，尤其是第一個(gè)節(jié)點(diǎn)死亡的時(shí)間延遲效果明顯。在上述仿真條件下重復(fù)實(shí)驗(yàn)50次，統(tǒng)計(jì)其第一個(gè)節(jié)點(diǎn)死亡時(shí)間（FD）和全部節(jié)點(diǎn)死亡時(shí)間（AD），得到如表數(shù)據(jù)，從數(shù)據(jù)結(jié)果可知，新算法在第一個(gè)節(jié)點(diǎn)死亡時(shí)間和全部節(jié)點(diǎn)死亡時(shí)間上比EEUC分別提高了17%、9%。

表1 網(wǎng)絡(luò)生命周期

修改仿真場(chǎng)景參數(shù)：在邊長(zhǎng)M=100 m的方形區(qū)域內(nèi)部署節(jié)點(diǎn)N=200個(gè)，其他條件不變，即不改變監(jiān)控區(qū)域大小而將節(jié)點(diǎn)密度增加1倍，得到數(shù)據(jù)如圖9。與圖8相比，圖9所示各算法的生命周期均有所延長(zhǎng)，這是由于當(dāng)節(jié)點(diǎn)密度增加后，各節(jié)點(diǎn)間的通信距離減小，使得通信能耗也隨之降低。從網(wǎng)絡(luò)生命周期來(lái)看，本案算法比EEUC算法在FD和AD上分別提高約24%和9%。從時(shí)間跨度上來(lái)講，LEACH和EEUC算法相對(duì)于低密度節(jié)點(diǎn)場(chǎng)景均有一定程度的增加，這是由于隨著節(jié)點(diǎn)密度的增大，整個(gè)網(wǎng)絡(luò)的層次結(jié)構(gòu)和簇成員數(shù)量也相應(yīng)增加，致使簇頭能量消耗加快，使網(wǎng)絡(luò)能耗的均衡性能下降。而本案算法在節(jié)點(diǎn)密度增大時(shí)，第一個(gè)節(jié)點(diǎn)死亡和全部節(jié)點(diǎn)死亡的時(shí)間跨度增加較小，這說(shuō)明算法在節(jié)點(diǎn)高密度條件下的能量均衡性能和能量效率更優(yōu)。

圖9 N=200時(shí)生命周期比較圖

3.2 參數(shù)分析

此節(jié)分析了基準(zhǔn)半徑R0與調(diào)節(jié)參數(shù)w對(duì)本文算法的影響。首先是對(duì)R0的分析。

半徑遞增有向成簇算法的提出中，引入了一個(gè)新的參數(shù)——基準(zhǔn)半徑R0，算法的的一個(gè)核心內(nèi)容是在半徑R0的范圍內(nèi)組簇，R0直接決定了簇的大小和簇的數(shù)量，所以在應(yīng)用和仿真中應(yīng)該首先給出參數(shù)R0的值。在具體的應(yīng)用與仿真中，由于監(jiān)控區(qū)域的規(guī)模、節(jié)點(diǎn)的密度等條件的不同，R0的最優(yōu)值并不是固定不變的。

在上述M=100 m，E=0.5J，基站（150，50）條件下，分別對(duì)N=100和N=200兩個(gè)場(chǎng)景仿真，R0從10 m到40 m按步長(zhǎng)2 m遞增，對(duì)每個(gè)值進(jìn)行10次實(shí)驗(yàn)，得到其第一個(gè)節(jié)點(diǎn)死亡的平均時(shí)間（輪數(shù)）的變化，如圖10和圖11。

圖10 N=100時(shí)第一個(gè)節(jié)點(diǎn)死亡時(shí)間隨R0變化圖

圖11 N=200時(shí)第一個(gè)節(jié)點(diǎn)死亡時(shí)間隨R0變化圖

從圖10和圖11中可以看到，當(dāng)基準(zhǔn)半徑R0的取值從10 m到25 m左右時(shí)，第一個(gè)節(jié)點(diǎn)死亡的時(shí)間逐漸延遲，這是因?yàn)殡S著基準(zhǔn)半徑R0的增大，簇類結(jié)構(gòu)在路由結(jié)構(gòu)中所占的比例也越來(lái)越高，分簇路由的優(yōu)勢(shì)在算法中的優(yōu)勢(shì)得到更多體現(xiàn)。當(dāng)基準(zhǔn)半徑R0的取值從25 m左右繼續(xù)增大時(shí)，第一個(gè)節(jié)點(diǎn)死亡的時(shí)間是逐漸提前的，尤其是在R0=30 m左右時(shí)，出現(xiàn)斷崖式的下降，原因在于隨著基準(zhǔn)半徑R0的繼續(xù)增加，分簇結(jié)構(gòu)在網(wǎng)絡(luò)路由中所占比例過(guò)大，擠壓了鏈?zhǔn)浇Y(jié)構(gòu)的比重，前文所述的前向傳輸思想的應(yīng)用范圍逐漸縮小，導(dǎo)致網(wǎng)絡(luò)生命周期大大縮短。尤其是當(dāng)R0=30 m以后，路由結(jié)構(gòu)中簇在直徑達(dá)到60 m以上，這跟LEACH算法已經(jīng)十分類似。

通過(guò)對(duì)比還可以看到，圖11比圖10在相同的基準(zhǔn)半徑條件下第一個(gè)節(jié)點(diǎn)死亡的時(shí)間均有所延遲，即網(wǎng)絡(luò)生命周期延長(zhǎng)，原因是在于節(jié)點(diǎn)密度增大后，節(jié)點(diǎn)間的通信距離減小，通信能耗也相應(yīng)減小，利于延長(zhǎng)網(wǎng)絡(luò)生命周期。另外，在節(jié)點(diǎn)數(shù)量N=100條件下，基準(zhǔn)半徑在20 m～24 m左右時(shí)第一個(gè)節(jié)點(diǎn)死亡時(shí)間最遲，最佳基準(zhǔn)半徑為R0=22 m；在節(jié)點(diǎn)數(shù)量N=200條件下，基準(zhǔn)半徑在22 m～26 m左右時(shí)網(wǎng)絡(luò)生命周期是長(zhǎng)，最佳基準(zhǔn)半徑R0=24 m。說(shuō)明隨著節(jié)點(diǎn)密度的增大，最佳基準(zhǔn)半徑也有所增大，這是由于密度增大時(shí)，相同半徑內(nèi)的鄰節(jié)點(diǎn)也會(huì)越多，各個(gè)簇內(nèi)的成員節(jié)點(diǎn)也越多，由于數(shù)據(jù)融合而節(jié)省的能量也更多，在相同總能量的條件下，節(jié)省的這部分能量可以使節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到更遠(yuǎn)的距離，基準(zhǔn)半徑的值也相應(yīng)的增大。

然后分析了w對(duì)算法的影響。w調(diào)節(jié)參數(shù)，取值范圍為［0，1］。w越小，對(duì)被選節(jié)點(diǎn)能量要求越低，那么符合條件的備選節(jié)點(diǎn)數(shù)量也就越多，反之亦然。為確定w對(duì)算法的影響，采用前述M=100 m仿真場(chǎng)景，令w從0按步長(zhǎng)0.05增加到1時(shí)，記錄其第一個(gè)節(jié)點(diǎn)死亡的平均時(shí)間（輪數(shù)）的變化，如圖12。

圖12 第一個(gè)節(jié)點(diǎn)死亡時(shí)間隨參數(shù)w變化圖

從圖中可知，w從0增加到0.2的過(guò)程中，第一個(gè)節(jié)點(diǎn)死亡的平均時(shí)間逐漸延遲，這是由于算法對(duì)簇頭或父節(jié)點(diǎn)具有一定的能量要求，過(guò)低能量的節(jié)點(diǎn)擔(dān)任簇頭或父節(jié)點(diǎn)會(huì)快速死亡，增加網(wǎng)絡(luò)重組頻率；隨著w從0.2繼續(xù)增大，越來(lái)越多的節(jié)點(diǎn)達(dá)不到該能量閾值，使得一些能量較高但位置不合理的節(jié)點(diǎn)被選為簇頭或下一跳節(jié)點(diǎn)，增加了節(jié)點(diǎn)間的通信距離，從而影響了網(wǎng)絡(luò)生命周期，所以0.2為在該應(yīng)用場(chǎng)景條件下的最優(yōu)值。

4 結(jié)束語(yǔ)

文中通過(guò)對(duì)分簇路由和鏈?zhǔn)铰酚傻膬?yōu)、缺點(diǎn)進(jìn)行分析，提出一種基于半徑遞增有向成簇的無(wú)線傳感器網(wǎng)絡(luò)路由算法。算法按照“向基站方向成鏈，鏈中盡量成簇”的基本思路，生成一種簇、鏈、樹相結(jié)合的混合路由結(jié)構(gòu)。實(shí)驗(yàn)證明，新算法能夠有效優(yōu)化路由結(jié)構(gòu)，在能量效率和均衡性能兩個(gè)方面更具優(yōu)勢(shì)，能夠?qū)⒕W(wǎng)絡(luò)生命周期提高9-17%，且在傳感器節(jié)點(diǎn)高密度部署的無(wú)線傳感器網(wǎng)絡(luò)中表現(xiàn)更優(yōu)。

［1］Akvildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Se?nor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［2］倪文亞，劉慶威，劉漫丹.基于能量和距離的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.2015，41（1）：84-88.

［3］靳淑娟.無(wú)線傳感器網(wǎng)絡(luò)中的能量均衡路由協(xié)議研究［D］.大連：大連理工大學(xué)，2009.

［4］王汝傳，孫力娟，黃海平，等.無(wú)線傳感器網(wǎng)絡(luò)中間件技術(shù)［M］.北京：科學(xué)出版社，2011.

［5］Heinzelman W，Handrakasan A，Alakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks［C］//Proceedings of the Hawaii Internationnal Conference on System Sciences，LosAlamitos，CA，USA：IEEE Computer Society，2000：3005-3014.

［6］Lindsey S，Raghavendra C.PEGASIS：Power Efficient Gathering in Sensor Information Systems［C］//Proceedings of the IEEE Aero?space Conference，Vol.3，May 2002.1125-1130.

［7］Ossama Y，Sonia F.HEED：A Hybird，Energy-Efficient，Distribut?ed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366-379.

［8］Manjeshwar A，Agrawal D P.TEEN：A Routing Protocol for En?hanced Efficiency in Wireless Sensor Networks［C］//Proceedings of the15th International Parallel and Distributed Processing Sym?posium（IPDPS），San Francisco，2001：2009-2015.

［9］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（1）：27-36.

［10］劉鐵流，巫永群.基于能量?jī)?yōu)化的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24（5）：764-770.

［11］嚴(yán)英，郭麗，許建真.一種基于LEACH與PEGASIS協(xié)議的分層成鏈優(yōu)化路由算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24（9）：1311-1316.

［12］劉東江，賈卓生.基于分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議的研究［J］.計(jì)算機(jī)學(xué)報(bào)，2012，39（10）：23-38.

［13］史久根，胡小博.高效節(jié)能的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議［J］.電子測(cè)量與儀器學(xué)報(bào)，2012（5）：437-445.

［14］Heinzelman W B，Chandrakasan A，Balakrishman H.An Applica?tion-Specific Protocol Architecture for Wireless Microsensor Net?works［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［15］Soro S，Einzelman W B.Prolonging the Lifetime of Wireless Sen?sors Networks Via Unequal Clustering［J］.Proc of the 19th IEEE International on Parallel and Distributed Processing Symposium.San Francisco：IEEE Computer Society Press，2005：236-240.

［16］張德干，張曉丹，李光.無(wú)線傳感與路由技術(shù)［M］.北京：科學(xué)出版社，2013.

［17］周則順，李臘元，許毅，等.無(wú)線傳感器網(wǎng)絡(luò)中能量有效分簇路由算法［J］.武漢理工大學(xué)學(xué)報(bào)，2011，35（6）：1157-1160.

［18］韓萬(wàn)強(qiáng)，劉云.WSN中基于分簇的路由改進(jìn)協(xié)議［J］.計(jì)算機(jī)工程，2012，38（5）：105-113.