王飛飛，孫志遠(yuǎn)

(平頂山學(xué)院，河南平頂山467000)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)[1]與傳統(tǒng)網(wǎng)絡(luò)不同，是集數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)傳輸于一體的復(fù)雜系統(tǒng)，它改變了與人自然的交互方式[2]。在WSN中，數(shù)據(jù)收集是網(wǎng)絡(luò)應(yīng)用的基本功能，傳感器節(jié)點(diǎn)(sensor node)之間相互協(xié)作，將其監(jiān)測到的多種環(huán)境信息傳送到基站，由于節(jié)點(diǎn)一般部署在惡劣或危險的環(huán)境中且節(jié)點(diǎn)采用能量有限的電池供電，能量難以二次補(bǔ)充，為了延長網(wǎng)絡(luò)生存時間，在算法設(shè)計時研究者應(yīng)以合理有效利用有限能量為首要目標(biāo)，因此基于分簇的思想被應(yīng)用在路由協(xié)議中，簇結(jié)構(gòu)的使用可以有效地增加網(wǎng)絡(luò)的可擴(kuò)展性，與平面算法相比，可以使網(wǎng)絡(luò)變得比較靈活，降低承擔(dān)路由的節(jié)點(diǎn)數(shù)目，減少能耗。目前已經(jīng)有許多學(xué)者對其進(jìn)行了深入的研究，目前經(jīng)典的分簇算法包括LEACH[3]、PEGASIS[4]、HEED[5]、CODA[6]等，與平面路由相比，可以減少節(jié)點(diǎn)能耗、延長網(wǎng)絡(luò)壽命，但同時也各自存在缺陷：LEACH隨機(jī)選擇簇首，沒有考慮到節(jié)點(diǎn)剩余能量，簇首與基站直接通信;PEGASIS協(xié)議中各節(jié)點(diǎn)通過貪婪算法成鏈，簇首為鏈上的節(jié)點(diǎn)之一，一旦簇首死亡則數(shù)據(jù)無法正常傳輸;HEED協(xié)議在成簇階段需廣播多條信息，增大了能量消耗;CODA需要知道所有節(jié)點(diǎn)的位置，擴(kuò)展性不好。本文在對現(xiàn)有協(xié)議研究的基礎(chǔ)上提出了一種基于能量均衡的WSN分簇路由算法CRAE(Cluster Routing Algorithm Based Energy Balance)，在該算法中，采用新的簇首競爭機(jī)制，簇形成后，簇間采用基于鏈路質(zhì)量的多跳路由。仿真結(jié)果表明該算法可以延緩節(jié)點(diǎn)死亡，有效利用能量。

1 系統(tǒng)模型

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

1)傳感器網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò)，節(jié)點(diǎn)部署后不再移動且可擴(kuò)充新節(jié)點(diǎn)，節(jié)點(diǎn)具有唯一ID;

2)節(jié)點(diǎn)具有相似能量E，地位平等，節(jié)點(diǎn)類型同構(gòu)但能量不能二次補(bǔ)充;

3)每輪中節(jié)點(diǎn)能耗不同;

4)各節(jié)點(diǎn)通信半徑為R，無線發(fā)射功率可調(diào)，例如Berkeley Motes節(jié)點(diǎn)，它經(jīng)由ioctl系統(tǒng)調(diào)用設(shè)置發(fā)射功率;

5)網(wǎng)絡(luò)中節(jié)點(diǎn)時間同步，具有數(shù)據(jù)融合能力，周期性進(jìn)行數(shù)據(jù)傳輸;

6)該網(wǎng)絡(luò)以考慮節(jié)點(diǎn)能量與均衡網(wǎng)絡(luò)能耗為首要目標(biāo)，不考慮數(shù)據(jù)傳輸失敗、節(jié)點(diǎn)通信安全等問題。

1.2 能量傳輸模型

該算法與LEACH協(xié)議所用通信模型相同，發(fā)送k bit數(shù)據(jù)與接收k bit的數(shù)據(jù)消耗能量公式如下：

在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能耗主要有接收能耗、發(fā)送能耗、數(shù)據(jù)融合能耗以及計算存儲能耗等，其中以發(fā)送能耗與接收能耗為主，同時由式(1)可知，節(jié)點(diǎn)發(fā)送能耗遠(yuǎn)大于接收能耗，因此，在進(jìn)行路由算法研究時要構(gòu)建合適的路由以有效合理地利用節(jié)點(diǎn)能量。

2 算法描述

在分簇網(wǎng)絡(luò)中，簇首需要管理簇內(nèi)成員、協(xié)調(diào)數(shù)據(jù)傳輸、進(jìn)行數(shù)據(jù)融合，還需要承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù)，因此與普通節(jié)點(diǎn)相比，簇首能耗較大。在該算法中，以節(jié)點(diǎn)的剩余能量為主要依據(jù)選擇簇首、成簇以及構(gòu)建數(shù)據(jù)傳輸時的簇間路由。具體算法描述如下。

2.1 簇首選擇

LEACH協(xié)議以隨機(jī)產(chǎn)生閾值的方式選擇簇首，但是該種算法適用的能量同構(gòu)網(wǎng)絡(luò)在實(shí)際應(yīng)用中并不存在，因此有的分簇算法[5-7]在節(jié)點(diǎn)閾值產(chǎn)生時引入節(jié)點(diǎn)的剩余能量，但是僅以剩余能量為依據(jù)選擇簇首不能保證在所有情況下都能有效延長網(wǎng)絡(luò)壽命?；诖?，本文算法以節(jié)點(diǎn)剩余能量與其鄰節(jié)點(diǎn)平均能量為競爭參數(shù)。

根據(jù)文獻(xiàn)[8]可知，無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域中理想的簇首個數(shù)為

簇的理想半徑為

每輪開始工作時，節(jié)點(diǎn)Si以半徑為r廣播消息Msg，Msg中包括節(jié)點(diǎn)ID與節(jié)點(diǎn)剩余能量Eresidual，r范圍內(nèi)的所有節(jié)點(diǎn)被看做Si的鄰節(jié)點(diǎn)，每個節(jié)點(diǎn)根據(jù)接收到的信息更新鄰節(jié)點(diǎn)表Ti后，計算得出其鄰節(jié)點(diǎn)的平均能量Si×Eave。在本文算法中，簇首競爭公式為(參數(shù)設(shè)置同文獻(xiàn)[7])

在簇首選擇階段，節(jié)點(diǎn)Si產(chǎn)生一個位于0～1之間的隨機(jī)數(shù)n：

當(dāng)n＜T(s)時，Si被選為簇首并廣播信息，信息中包含節(jié)點(diǎn)ID，簇首標(biāo)識CH;

當(dāng)n＞=T(s)時，Si根據(jù)收到的廣播信息判斷自己理想半徑范圍內(nèi)是否存在簇首，如果存在，該節(jié)點(diǎn)為普通節(jié)點(diǎn)，否則，Si成為簇首，并廣播信息。

2.2 成簇策略

在成簇階段，簇首節(jié)點(diǎn)以半徑r廣播成簇信息，由于WSN的特性，網(wǎng)絡(luò)節(jié)點(diǎn)密度較大，可能存在某些節(jié)點(diǎn)同時接收到來自多個簇首的信息，在現(xiàn)有的成簇算法中，有以簇首剩余能量為依據(jù)的，有以到簇首距離為依據(jù)的，也有將二者綜合進(jìn)行比較的。在本文算法中，簇首選擇已將能量因素考慮在內(nèi)，因此普通節(jié)點(diǎn)選擇距離較近的簇首作為其簇首節(jié)點(diǎn)。

2.3 數(shù)據(jù)傳輸

該算法在數(shù)據(jù)傳輸時，在LEPS[10]算法的基礎(chǔ)上進(jìn)行動態(tài)路由構(gòu)建。LEPS以最小跳數(shù)為標(biāo)準(zhǔn)建立簇首節(jié)點(diǎn)到基站的最短路徑，選擇父節(jié)點(diǎn)時以鏈路質(zhì)量為依據(jù)，在減少時延的同時保證了數(shù)據(jù)的可靠傳輸，但是沒有考慮到節(jié)點(diǎn)的可利用能量與路由的動態(tài)性。

該算法在路由構(gòu)建時首先確定每個簇首到基站的最小跳數(shù)，然后確定每個簇首通往基站的父節(jié)點(diǎn)集合，以節(jié)點(diǎn)Si為例，其父節(jié)點(diǎn)選取公式

式中：Ei為Si的剩余能量;Ki為向P發(fā)送數(shù)據(jù)包數(shù);d為Si到父節(jié)點(diǎn)P的距離。距離越小，傳輸信號質(zhì)量越好，距離越大，傳輸信號質(zhì)量越差，應(yīng)盡量將d控制在d0內(nèi)[9]，否則不僅信號質(zhì)量差，而且大大增加簇首發(fā)送數(shù)據(jù)的能耗。一次選擇完畢，在余下的節(jié)點(diǎn)中進(jìn)行再次選擇，即為每個節(jié)點(diǎn)選擇兩個可供數(shù)據(jù)傳輸?shù)母腹?jié)點(diǎn)。

在本文算法中，采用兩輪數(shù)據(jù)傳輸后再重新成簇的方法。在首輪進(jìn)行數(shù)據(jù)傳輸時，簇首在父節(jié)點(diǎn)集合中隨機(jī)選擇其中一個作為中轉(zhuǎn)節(jié)點(diǎn)，并為其加狀態(tài)標(biāo)記;在第二次進(jìn)行數(shù)據(jù)傳輸時則選擇另外一個節(jié)點(diǎn)，這樣可以減少簇首選擇及節(jié)點(diǎn)計算能耗。

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

3.1 仿真環(huán)境

為了評估該算法的性能，通過OMNET++仿真平臺下的模擬實(shí)驗(yàn)將其與現(xiàn)有的LEACH、HEED算法進(jìn)行比較分析。假定400個傳感器節(jié)點(diǎn)均勻散布在200×200區(qū)域中，基站位置為(50，250)，節(jié)點(diǎn)均為靜止。通信常量設(shè)置為Eelec=50 nJ/bit，節(jié)點(diǎn)的初始能量為0.5 J，數(shù)據(jù)包大小為4 000 bit，數(shù)據(jù)融合能耗為5 nJ/bit/signal，傳輸放大器的能耗為10 pJ/bit/m2。

3.2 仿真結(jié)果分析

圖1顯示了在隨機(jī)抽取的10輪中，每輪全網(wǎng)節(jié)點(diǎn)最大能量值與最小能量值的方差計算公式為

在式(2)中，emax、emin分別是全網(wǎng)節(jié)點(diǎn)的最大剩余能量與最小剩余能量。方差值小則說明網(wǎng)絡(luò)均衡度較好。由圖1可知，LEACH的方差值最高，而且差距明顯較大，這是因?yàn)長EACH隨機(jī)選擇簇首，不能很好的控制能量均衡消耗。CRAE的方差最低是因?yàn)樵搮f(xié)議在選擇簇首時考慮到節(jié)點(diǎn)的剩余能量與鄰節(jié)點(diǎn)的平均能量，并且在數(shù)據(jù)傳輸時考慮到中轉(zhuǎn)節(jié)點(diǎn)的能量問題，因此更好的均衡了網(wǎng)絡(luò)能耗。

圖2給出了三種算法的全網(wǎng)存活節(jié)點(diǎn)個數(shù)隨時間的變化趨勢。在傳感器網(wǎng)絡(luò)中，設(shè)計算法以延長節(jié)點(diǎn)及全網(wǎng)的生存時間為主要目標(biāo)，由于CRAE采用新的簇首競爭策略與多跳路由，使得各節(jié)點(diǎn)能量消耗較為均衡，所以在多輪工作后，存活節(jié)點(diǎn)個數(shù)仍較多，與另外兩種算法相比，推遲了第一個節(jié)點(diǎn)的死亡，同時縮短了第一個節(jié)點(diǎn)與最后一個節(jié)點(diǎn)死亡的時間間距。

4 結(jié)束語

本文在對現(xiàn)有無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究基礎(chǔ)上，提出了一種新的基于能量均衡的WSN分簇路由算法，該算法依據(jù)節(jié)點(diǎn)的剩余能量與鄰節(jié)點(diǎn)平均能量選擇簇首，并且在傳輸過程中綜合考慮了簇首與基站的最小跳數(shù)以及中轉(zhuǎn)節(jié)點(diǎn)的能量問題。實(shí)驗(yàn)表明，該算法與LEACH、HEED協(xié)議相比，優(yōu)化了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)生存時間。

[1] 孫建民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2006.

[2] Akyildiz I F，Su W，Sankarasubramaniam Y，Cayirci E.Wireless sensor networks：A survey[J].Computer Networks，2002，38(4)：393-422.

[3] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks[C]//IEEE Proceedings of the Hawaii International Conference System Sciences.Hawaii，2000：3005-3014.

[4] Lindsey S，Raghavendra C.PEGASIS：power efficient gathering in sensor information systems[C]//Proceedings of the IEEE Aerospace Conference’02.Montana，2002：1125-1130.

[5] Younis O，F(xiàn)ahmy S.Heed：A hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks[J].IEEE Trans on Mobile Computing，2004，3(4)：660-669.

[6] Ngo H Q，Lee Y K，Lee S Y.MEPA：A new protocol for energy-efficient，distributed clustering in wireless sensor networks[C]//Proc of the IEEE Int’l Symp.on Wireless Communication Systems.Norway：Wireless Communication Systems，2007.40-44.

[7] Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proc of the 4th IEEE Conf.on Mobile and Wireless Communications Networks.Stockholm：IEEE Communications Society，2002：368-372.

[8] Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4)：660-670.

[9] 顏庭莘，孫利民.TinyOS路由協(xié)議原理及性能評估[J].計算機(jī)工程，2007，33(1)：112-114.