董國(guó)勇，彭 力，吳 凡，聞繼偉

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫214122)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)節(jié)點(diǎn)由于能量受限等特點(diǎn)嚴(yán)重影響了其網(wǎng)絡(luò)性能，因此，WSNs協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地使用傳感器節(jié)點(diǎn)的能量，延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間。

研究人員們陸續(xù)提出了分簇路由協(xié)議［1～3］。Heinzelman W 等人［1］提出的LEACH 分簇路由協(xié)議隨機(jī)選舉簇首，收集簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)并融合后發(fā)送給觀察者來(lái)減少能耗。Younis O 等人［4］提出一種混合式的分簇協(xié)議HEED，算法根據(jù)節(jié)點(diǎn)剩余能量來(lái)概率性地選取一些候選簇首，然后以簇內(nèi)部通信代價(jià)的高低來(lái)競(jìng)爭(zhēng)產(chǎn)生最終簇首。LEACH-CS［5］以跨區(qū)距離的約束來(lái)自定義合適的多跳路由方案，通過(guò)均勻分簇、多跳路由一定程度上平衡了簇首的能量消耗，但是距離Sink 節(jié)點(diǎn)近的簇首會(huì)因轉(zhuǎn)發(fā)大量數(shù)據(jù)而能耗較大，容易導(dǎo)致“熱區(qū)”問(wèn)題。

針對(duì)這一問(wèn)題，李成法等人提出了EEUC［6］非均勻分簇路由算法。依據(jù)節(jié)點(diǎn)距基站的遠(yuǎn)近構(gòu)建大小不等的簇，離基站越近簇半徑越小，簇內(nèi)成員越少，為簇首間數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量。然而，算法是隨機(jī)地挑選候選簇首，并沒(méi)有考慮到節(jié)點(diǎn)分布的不均勻性。

文獻(xiàn)［7］提出的WSNs 中基于能量代價(jià)的能量?jī)?yōu)化路由算法在選擇平面路由時(shí)利用了節(jié)點(diǎn)間能量代價(jià)函數(shù)和前向區(qū)域來(lái)選擇下一跳節(jié)點(diǎn)。文獻(xiàn)［8］提出的能量均衡的WSNs 非均勻分簇路由協(xié)議分簇時(shí)采用了定時(shí)機(jī)制，一定程度上減少了信息交互量。然而，在選擇中繼節(jié)點(diǎn)時(shí)沒(méi)有考慮到節(jié)點(diǎn)間的負(fù)載均衡。

針對(duì)以上算法存在的一些問(wèn)題，本文提出了一種基于權(quán)值和代價(jià)函數(shù)的WSNs 非均勻分簇路由(uneven clustering routing based on weight and cost function，WCF-UC)算法，算法考慮節(jié)點(diǎn)剩余能量與節(jié)點(diǎn)密度計(jì)算簇首競(jìng)爭(zhēng)權(quán)值。用一個(gè)代價(jià)函數(shù)，綜合考慮簇首剩余能量、簇內(nèi)成員節(jié)點(diǎn)數(shù)和位置信息等，決定每個(gè)簇首下一跳節(jié)點(diǎn)的最優(yōu)路徑。

1 系統(tǒng)模型

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

假設(shè)N 個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)M×M 的正方形區(qū)域內(nèi)，且該網(wǎng)絡(luò)具有以下性質(zhì):1)節(jié)點(diǎn)可感知自身剩余能量;2)相鄰節(jié)點(diǎn)采集的數(shù)據(jù)有相似性，可進(jìn)行數(shù)據(jù)融合處理;3)鏈路是對(duì)稱的，節(jié)點(diǎn)可根據(jù)RSSI 計(jì)算出發(fā)送者到自身的近似距離;4)節(jié)點(diǎn)可根據(jù)需要調(diào)整自身發(fā)射功率。

1.2 能量消耗模型

本文與文獻(xiàn)［9，10］使用了類似的無(wú)線通信模型，發(fā)送需要消耗的能量為

接收需要消耗的能量為

其中，Eelec為發(fā)送電路和接收電路消耗的能量，εfs，εmp分別為自由空間傳播模型和多路徑衰減傳播模型的能耗，為融合單位比特?cái)?shù)據(jù)消耗的能量。

2 WCF-UC 算法基本思想

2.1 簇首選擇與簇的建立

算法通過(guò)候選簇首競(jìng)爭(zhēng)方式?jīng)Q定最終簇首，根據(jù)節(jié)點(diǎn)與基站距離及剩余能量來(lái)決定節(jié)點(diǎn)競(jìng)爭(zhēng)半徑?？拷镜拇厥滓袚?dān)更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，為了節(jié)省該簇首的能耗，需要保證節(jié)點(diǎn)有較高的能量同時(shí)縮小競(jìng)爭(zhēng)半徑，即根據(jù)公式(3)

其中，dmax，dmin分別為節(jié)點(diǎn)到Sink 節(jié)點(diǎn)的最大和最小距離，d(si，DS)為節(jié)點(diǎn)到Sink 節(jié)點(diǎn)的距離，R0c 為競(jìng)爭(zhēng)半徑最大值，c 為0 ～1 可控制取值的參數(shù)，Eini，Ei，Emin分別為節(jié)點(diǎn)初始能量、剩余能量、設(shè)置的最低工作能量。

競(jìng)爭(zhēng)簇首時(shí)，須同時(shí)考慮節(jié)點(diǎn)剩余能量、充當(dāng)簇首后能耗及整個(gè)區(qū)域平均剩余能量。節(jié)點(diǎn)剩余能量越大，競(jìng)爭(zhēng)機(jī)會(huì)越大;節(jié)點(diǎn)越密集，該區(qū)域成簇的可能性越大。節(jié)點(diǎn)計(jì)算收到的各個(gè)候選簇首的競(jìng)爭(zhēng)權(quán)值，選擇較大的作為簇首并加入。競(jìng)爭(zhēng)權(quán)值如式(4)

式中 Wn為簇首競(jìng)爭(zhēng)權(quán)值，Ecurrent，Eini分別為該節(jié)點(diǎn)剩余能量和初始能量，α 為小于1 的常數(shù)，經(jīng)過(guò)實(shí)驗(yàn)，取0.85 時(shí)簇首效果最佳;Kc為最佳簇首個(gè)數(shù)，M 為節(jié)點(diǎn)覆蓋區(qū)域面積，dtoBS為網(wǎng)絡(luò)中心到基站的距離。這里，引入節(jié)點(diǎn)密度的概念［11，12］，即節(jié)點(diǎn)在某一范圍內(nèi)的存活鄰居節(jié)點(diǎn)數(shù)占所有存活節(jié)點(diǎn)總數(shù)的比重，Qn為節(jié)點(diǎn)密度。在每個(gè)周期開(kāi)始，節(jié)點(diǎn)對(duì)外廣播，收集半徑為RC范圍內(nèi)的存活節(jié)點(diǎn)信息，同時(shí)將自身存活情況報(bào)告給鄰居節(jié)點(diǎn)。這樣可以得到Neighbor(n)alive.RC通過(guò)公式(2)獲得。Networkalive可以通過(guò)基站在獲得所有節(jié)點(diǎn)自身情況時(shí)，廣播給網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)。

2.2 簇內(nèi)數(shù)據(jù)通信

簇內(nèi)節(jié)點(diǎn)交換數(shù)據(jù)時(shí)，簇首將簇內(nèi)成員節(jié)點(diǎn)連成一條數(shù)據(jù)傳輸鏈，成員節(jié)點(diǎn)從傳輸鏈的兩端向簇首傳送數(shù)據(jù)，因此，簇首只需和鄰近的成員節(jié)點(diǎn)各收發(fā)一次數(shù)據(jù)。假設(shè)在第a 輪采集過(guò)程中，第i 個(gè)簇有n 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)每次采集k bit 數(shù)據(jù)，那么，簇首在這次數(shù)據(jù)采集過(guò)程中接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)和數(shù)據(jù)融合能量的消耗為

而簇內(nèi)節(jié)點(diǎn)以點(diǎn)對(duì)點(diǎn)的方式向簇首傳輸數(shù)據(jù)時(shí)，簇首的能量消耗為

由上式可知，n?3，所以，采用上述算法后，簇首消耗能量將大大減小，可以有效平衡簇首與成員節(jié)點(diǎn)的能耗。

2.3 簇間多跳路由

本算法多跳路由設(shè)計(jì)目標(biāo)是為了找到一條最優(yōu)化路徑，以減小簇間數(shù)據(jù)傳輸時(shí)的能耗和避免“熱點(diǎn)”問(wèn)題。首先，簇首Hi在競(jìng)爭(zhēng)范圍內(nèi)廣播一條消息，包括簇內(nèi)節(jié)點(diǎn)數(shù)、簇首ID、剩余能量和基站距離。若鄰居簇首到基站的距離較小，那么，簇首Hi計(jì)算和鄰居簇首Hj的距離，并且建立一張包含鄰居簇首信息表。

Hi在鄰居簇首集中選擇下一跳節(jié)點(diǎn)NHi，該節(jié)點(diǎn)在所有的鄰居簇首中具有最小的代價(jià)函數(shù)。代價(jià)函數(shù)如下定義

式中 Eavr(Hi)表示簇首Hi鄰居簇首的剩余能量均值，Ecurrent(Hj)為簇首Hj的剩余能量，Nc(Hj)為簇首Hj的成員節(jié)點(diǎn)數(shù)，Nc_avr(Hi)為簇首Hi鄰居簇首平均節(jié)點(diǎn)數(shù)，dHi-Hj為Hi到Hj的距離，dHj-BS為Hj到基站的距離，α，β，γ 為加權(quán)系數(shù)，滿足α+β+γ=1。代價(jià)函數(shù)第一項(xiàng)是為了選擇剩余能量較大的簇首作為下一跳節(jié)點(diǎn)，因?yàn)橄乱惶?jié)點(diǎn)需要轉(zhuǎn)發(fā)數(shù)據(jù)消耗更多能量，所以，能量因素是首要考慮的;第二項(xiàng)是為了選擇成員節(jié)點(diǎn)數(shù)量較少的作為下一跳，這樣簇內(nèi)通信能耗較少，有更多能量用于轉(zhuǎn)發(fā)數(shù)據(jù);第三項(xiàng)主要是為了下一跳節(jié)點(diǎn)位置的考慮，多跳路由應(yīng)該盡量選擇最短路徑，使得傳輸能耗最小。如果Hi的下一跳為本身，那么，直接發(fā)送數(shù)據(jù)到基站;否則，將數(shù)據(jù)發(fā)往下一跳節(jié)點(diǎn)，所有節(jié)點(diǎn)都找到下一跳節(jié)點(diǎn)后，簇間多跳路由建立完成。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文在Matlab 平臺(tái)下仿真實(shí)驗(yàn)，將500 個(gè)節(jié)點(diǎn)隨機(jī)分布在一個(gè)200 m×200 m 區(qū)域中，Sink 節(jié)點(diǎn)的坐標(biāo)為(100，250)m。實(shí)驗(yàn)參數(shù)如表1 所示。

表1 實(shí)驗(yàn)參數(shù)Tab 1 Experimental parameters

算法開(kāi)始，N×p 個(gè)節(jié)點(diǎn)成為候選簇廣播N×p 條競(jìng)選消息。每個(gè)候選簇首廣播一條競(jìng)選簇首成功消息，或廣播一條退出競(jìng)選消息通知鄰簇首，總N×p 條消息。設(shè)共k 個(gè)簇首，廣播k 條競(jìng)選獲勝消息，之后N-k 個(gè)普通節(jié)點(diǎn)發(fā)送N-k 條申請(qǐng)加入消息?？傆?jì)2N×p+N 條消息。與EEUC算法一樣，本文WCF-UC 也是消息驅(qū)動(dòng)的算法，消息復(fù)雜度仍為O(N)。

比較4 種算法的網(wǎng)絡(luò)生命周期。如圖1，LEACH 的第一個(gè)節(jié)點(diǎn)在305 輪死亡，HEED，EEUC，WCF-UC 算法分別為220 輪、480 輪和610 輪，WCF-UC 算法明顯延遲了首個(gè)節(jié)點(diǎn)失效時(shí)間。WCF-UC 算法最后一個(gè)節(jié)點(diǎn)的死亡輪數(shù)是1610 輪，EEUC，HEED，LEACH 算 法 分 別 為1190，1000，790 輪，相對(duì)于實(shí)驗(yàn)總輪數(shù)(1800 輪)，分別延遲了23.3%，33.9%，45.6%。由此可見(jiàn)，WCF-UC 有效提高了能量的均衡性，延長(zhǎng)了網(wǎng)絡(luò)生命周期。

圖1 網(wǎng)絡(luò)生命周期對(duì)比Fig 1 Comparison of network lifetime

簇首能耗占網(wǎng)絡(luò)能耗主要部分，因此，須對(duì)比4 種協(xié)議的簇首能耗之和。實(shí)驗(yàn)中隨機(jī)選取10 輪，統(tǒng)計(jì)各輪中所有簇首能耗和。如圖2，WCF-UC 和EEUC 算法的簇首能耗最低。因?yàn)閮煞N協(xié)議中，簇首采用多跳方式將數(shù)據(jù)發(fā)送至匯聚點(diǎn)，顯著降低了能耗。

圖2 簇首消耗能量之和對(duì)比Fig 2 Comparison of sum of cluster heads energy consumption

圖3 對(duì)比了4 種算法網(wǎng)絡(luò)剩余總能量隨周期的變化情況，LEACH 最先消耗為0。WCF-UC 比LEACH，HEED，EEUC 的能量消耗減少了30.3%，25.2%，10.6%。WCF-UC更有效地節(jié)約了能量，因?yàn)橥瑫r(shí)考慮了節(jié)點(diǎn)剩余能量、與基站距離及節(jié)點(diǎn)分布進(jìn)行簇首選擇與簇的建立，采用代價(jià)函數(shù)的多跳路由優(yōu)化了各簇首間的能量路徑。

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

本文基于權(quán)值和代價(jià)函數(shù)提出的非均勻分簇路由算法，有效減少了簇首選舉和路由數(shù)據(jù)轉(zhuǎn)發(fā)能耗。仿真分析表明:WCF-UC 算法網(wǎng)絡(luò)存活時(shí)間有明顯提高，能有效均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗。但是本文沒(méi)有考慮簇半徑的優(yōu)化等問(wèn)題，有待進(jìn)一步完善研究。

［1］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocols for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000:3005-3014.

［2］ Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［3］ Soro S，Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium，2005:236-243.

［4］ Younis O，F(xiàn)ahmy S.HEED:A hybrid，enegry-efficient，distribued clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):660-669.

［5］ 顧躍躍，白光偉，陶金晶.LEACH-CS:一種自定義的WSNs 跨區(qū)多跳路由機(jī)制［J］.計(jì)算機(jī)科學(xué)，2011，38(1):78-82.

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

［7］ 許彥芹，陳慶奎.基于SMP 集群的MPI+CUDA 模型的研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(15):3408-3412.

［8］ University of Illinois at Urbana-Champaign.Accelerator cluster webpage［EB/OL］.［2013—03—12］.http:∥iacat.illinois.edu/resources/cluster/.

［9］ Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An energy efficient clustering scheme in wireless sensor networks［C］∥IEEE International Performance Computing and Communications Conference(IPCCC)，2005:535-540.

［10］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000:1-10.

［11］喬俊峰，劉三陽(yáng)，曹祥宇.無(wú)線傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)密度的簇算法［J］.計(jì)算機(jī)科學(xué)，2009，36(12):46-49.

［12］盧先領(lǐng)，王瑩瑩，王洪斌，等.無(wú)線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法［J］.計(jì)算機(jī)科學(xué)，2013，40(5):78-81.