基于差分算法的無線傳感器網(wǎng)絡(luò)路由分簇協(xié)議

李志明 唐永中

(河西學(xué)院信息技術(shù)中心 甘肅 張掖 734000)

基于差分算法的無線傳感器網(wǎng)絡(luò)路由分簇協(xié)議

李志明 唐永中

(河西學(xué)院信息技術(shù)中心 甘肅 張掖 734000)

針對異構(gòu)無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議存在節(jié)點能耗不均衡問題，提出一種基于差分進化算法的路由協(xié)議及基于節(jié)點能耗的分簇協(xié)議。該協(xié)議首先以最大化網(wǎng)絡(luò)中簇頭節(jié)點的最小生存周期為目標(biāo)，建立函數(shù)優(yōu)化模型，并采用差分進化算法對其進行優(yōu)化，從而延長網(wǎng)絡(luò)整體的生存周期；然后根據(jù)節(jié)點通信列表中的簇頭數(shù)目進行分簇，將節(jié)點分配給能耗因子較低的簇頭，以達到均衡網(wǎng)絡(luò)能耗的目的，延長普通節(jié)點的生存周期。仿真結(jié)果表明，基于差分的路由分簇協(xié)議能有效均衡網(wǎng)絡(luò)中節(jié)點的能量消耗，顯著延長網(wǎng)絡(luò)的生存周期并提高網(wǎng)絡(luò)能量利用率。

異構(gòu)無線傳感器網(wǎng)絡(luò) 路由 分簇 差分算法

0 引 言

無線傳感器網(wǎng)絡(luò)受到了國內(nèi)外學(xué)者們的廣泛關(guān)注，它可以被應(yīng)用在環(huán)境監(jiān)測、醫(yī)療等領(lǐng)域[1]。然而由于傳感節(jié)點的能量有限，直接限制了網(wǎng)絡(luò)的工作時間。尤其在戰(zhàn)爭、森林等復(fù)雜環(huán)境里，節(jié)點很難被訪問、更換或充電。因此，對無線傳感器網(wǎng)絡(luò)來說，最大化網(wǎng)絡(luò)的工作時間是非常關(guān)鍵的問題。

為降低節(jié)點通信中的網(wǎng)絡(luò)能耗，廣泛使用的一種策略是分簇[2]，即網(wǎng)絡(luò)中的節(jié)點被組織分配到特定數(shù)量的獨立區(qū)域內(nèi)，每個區(qū)域選出一個負(fù)責(zé)接收、融合和轉(zhuǎn)發(fā)本區(qū)間內(nèi)的節(jié)點監(jiān)測信息的簇頭，每個節(jié)點只與一個簇頭連接，簇頭將融合后的信息通過單跳或多跳的方式傳輸給基站。如文獻[3]提出LEACH策略，通過周期性的選取簇頭的方式以平衡網(wǎng)絡(luò)中節(jié)點的能耗。然而由于節(jié)點攜帶能量較低，充當(dāng)簇頭的節(jié)點會較快地耗費掉自身能量，且頻繁更換簇頭有需要重新設(shè)計簇頭節(jié)點的路由通信鏈路，這會為網(wǎng)絡(luò)帶來較大的通信開銷。對此，文獻[4]提出了一種改進策略PEGASIS，該算法相比于LEACH雖能在一定程度上延長網(wǎng)絡(luò)生存周期，但是它需要對網(wǎng)絡(luò)進行動態(tài)拓?fù)湔{(diào)整，如果網(wǎng)絡(luò)中節(jié)點數(shù)量較多，則網(wǎng)絡(luò)延遲將會相當(dāng)大，因此該算法不適合于大規(guī)模傳感網(wǎng)絡(luò)。

為進一步解決網(wǎng)絡(luò)生存周期較低的問題，文獻[5-6]采用向網(wǎng)絡(luò)中布撒高能節(jié)點充當(dāng)簇頭節(jié)點，以延長網(wǎng)絡(luò)生存周期。 這種方式相比于同構(gòu)網(wǎng)絡(luò)雖然較大程度的延長了網(wǎng)絡(luò)壽命，但由于簇頭節(jié)點能耗較大，因此網(wǎng)絡(luò)壽命仍然面臨著能耗的限制，因此采用合理的路由拓?fù)浣Y(jié)構(gòu)和均衡的分簇算法對網(wǎng)絡(luò)顯得尤為重要，對此文獻[7]提出GLBCA算法；文獻[8]提出基于GA的路由分簇算法；文獻[9]提出的GAR算法。這三種算法雖然在一定程度上優(yōu)化了拓?fù)浣Y(jié)構(gòu)延長了網(wǎng)絡(luò)生存周期，然而都沒有從節(jié)點的生存周期這一根本目標(biāo)出發(fā)對網(wǎng)絡(luò)進行優(yōu)化。

基于以上分析，為降低節(jié)點在通信中的能耗、延長網(wǎng)絡(luò)生存周期，本文結(jié)合差分算法[9]較好的優(yōu)化性能，提出了基于差分的路由分簇算法。首先以最大化最小簇頭節(jié)點的生存周期為目標(biāo)，采用差分算法對其進行優(yōu)化，以盡量延長網(wǎng)絡(luò)中簇頭節(jié)點的最短生存周期；然后根據(jù)節(jié)點的能耗，建立了能耗因子，對每個節(jié)點進行分簇時，選擇能耗因子最小，也即能最好均衡普通節(jié)點和高能節(jié)點能耗的簇頭。實驗表明，本文算法能夠有效的均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)生存周期。

1 能耗模型

本文采用LEACH提出的能量模型[10]。假設(shè)發(fā)送端能耗包括信號處理和功率放大兩個部分，接收端能耗為信號處理和數(shù)據(jù)融合。則根據(jù)無線通信理論，兩個距離為d的傳感器節(jié)點之間發(fā)送和接受lbit數(shù)據(jù)時，發(fā)送端消耗的能量為:

(1)

其中，d0為判決閾值，εfsd2和εmpd4是發(fā)送每比特數(shù)據(jù)放大器的能量消耗，Eelec是每比特數(shù)據(jù)在發(fā)送電路和接收電路消耗的能量。節(jié)點接收l比特數(shù)據(jù)時的能量消耗如式(2)所示。

ER(l)=lEelec

(2)

2 基于DE的路由算法

對異構(gòu)無線傳感器網(wǎng)絡(luò)，由于受能量的限制，因此必須設(shè)計合理的拓?fù)浣Y(jié)構(gòu)降低節(jié)點能耗以延長網(wǎng)絡(luò)生命周期，對此本文提出了基于DE算法的路由算法以及基于簇頭節(jié)點能耗的分簇算法，距離過程描述如下。

2.1 基于差分的路由算法

假設(shè)網(wǎng)絡(luò)中的簇頭個數(shù)為5，當(dāng)簇頭gi與簇頭gj的距離滿足式(3)-式(4)，則說明兩個簇頭可進行通信且簇頭gj比gi更靠近基站，因此將gj存入gi的通信列表中。

dis(gi,gj)

(3)

dis(gj,BS)

(4)

則簇頭節(jié)點的可通信列表如表1所示。

表1 簇頭節(jié)點通信列表

則種群中的粒子Xi,d表示粒子i的第d個簇頭在選擇下一跳簇頭時的概率值，假設(shè)粒子i的初始化結(jié)果為[0.54,0.36,0.11,0.36,0.37]，則通過計算可得到網(wǎng)絡(luò)中簇頭節(jié)點的連接列表，具體如表2所示。

表2 簇頭選擇下一跳列表

當(dāng)采用差分算法對簇頭節(jié)點的通信鏈路進行規(guī)劃時，需要為算法設(shè)定目標(biāo)函數(shù)，因為異構(gòu)無線傳感器網(wǎng)絡(luò)首要考慮的因素是網(wǎng)絡(luò)生存周期，而簇頭節(jié)點不僅要接收轉(zhuǎn)發(fā)其他簇頭的信息包，還要接收轉(zhuǎn)發(fā)本簇內(nèi)節(jié)點的數(shù)據(jù)信息，因此簇頭節(jié)點的能量消耗較大。所以簇頭節(jié)點的工作時間，決定了傳感網(wǎng)絡(luò)的監(jiān)測效果，對此，本文將最大化簇頭節(jié)點的最短生命周期作為算法的目標(biāo)函數(shù)，具體如式(5)所示。

f=Max(min{(lifetime_gi)|?i,1≤i≤D})

(5)

其中，lifetime_gi表示簇頭節(jié)點gi在不考慮接收融合簇內(nèi)節(jié)點時的生存周期。則簇頭節(jié)點的網(wǎng)絡(luò)生存周期如式(6)所示。

lifetime_gi=E/(ER×NIN(gi)+(NIN(gi)+1)×ET(gi,NextHop(gi)))

(6)

其中，E表示簇頭節(jié)點的總能量；NIN(gi)表示簇頭gi接收到的來自其他簇頭的數(shù)據(jù)包的個；(gi,NextHop(gi))表示簇頭gi與它下一跳簇頭的距離。

2.2 基于能量的分簇算法

由式(1)可知，普通節(jié)點與其簇頭節(jié)點通信距離的不同，則在每輪通信中的能耗不同，也即具有不同的網(wǎng)絡(luò)周期；另外，簇頭節(jié)點接收和融合本簇內(nèi)節(jié)點時也需增加一定的能耗，且隨著簇內(nèi)節(jié)點數(shù)目的增多，簇頭節(jié)點的能耗壓力會逐漸增大。因此，為了使普通節(jié)點和高能節(jié)點的生存周期都達到最大，本文提出基于簇頭節(jié)點能耗的分簇算法，具體描述如下。

1) 根據(jù)普通節(jié)點的位置及它的通信距離得到每個普通節(jié)點可連接簇頭的通信列表；

2) 以列表中含有簇頭數(shù)目的多少為順序?qū)ζ胀ü?jié)點進行分簇，節(jié)點可連接的簇頭數(shù)越少，則可選擇簇頭的機會就越少，因此從連接矩陣較小的普通節(jié)點開始分簇；

3) 分簇時，要兼顧普通節(jié)點和簇頭節(jié)點的網(wǎng)絡(luò)生存周期，也即兼顧普通節(jié)點和簇頭節(jié)點在每輪通信中的能耗情況。當(dāng)將一個節(jié)點i分配給簇頭k時，一方面簇頭節(jié)點增加了接收和融合的能耗，另一方面節(jié)點Si的發(fā)送距離是基于與簇頭gk的距離計算的，因此對監(jiān)測節(jié)點來說，其可連接簇頭矩陣中必然存在一個能較好均衡節(jié)點能耗與簇頭能耗的簇頭節(jié)點，則將節(jié)點連接到該簇頭上。具體的衡量節(jié)點和簇頭能耗的能耗因子如式(7)所示：

lk=αEgk+βE(sk,gk)

(7)

其中Egk表示節(jié)點si的可連接簇頭列表中第gk個簇頭的總能耗；E(si,gk)表示將節(jié)點si分配給簇頭gk時的傳輸能耗；α和β表示普通節(jié)點生存周期和簇頭節(jié)點生存周期的權(quán)重因子。因為簇頭節(jié)點要接收轉(zhuǎn)發(fā)其它節(jié)點發(fā)來的信息，因此相比于普通節(jié)點，簇頭節(jié)點的生存周期應(yīng)受到更多的關(guān)注，當(dāng)計算完節(jié)點si與其矩陣中的簇頭gk之間的能耗因子后，將節(jié)點連接到能耗因子最小的簇頭上。通過實驗發(fā)現(xiàn)，當(dāng)α取值為0.8、β取值為0.2時，得到的實驗效果較好。

2.3 基于DE的路由分簇算法步驟

設(shè)網(wǎng)絡(luò)中簇頭節(jié)點的個數(shù)為D，種群規(guī)模為N，則基于差分的路由分簇算法的具體操作步驟如下：

1) 向網(wǎng)絡(luò)中布撒傳感節(jié)點，得到每個節(jié)點的位置坐標(biāo)；

2) 對比通信距離，得到每個簇頭的節(jié)點的可連接路由列表；

3) 對比通信距離，得到每個普通節(jié)點的可連接簇頭列表；

4) 種群初始化，采用差分算法對最大化最小簇頭生存周期進行優(yōu)化；

5) 根據(jù)差分算法得到的最優(yōu)值，得到路由通信列表并得到此時每個簇頭節(jié)點在每輪通信中的能耗；

6) 對每個普通節(jié)點，按照其簇頭集合的規(guī)模并通過比較能耗因子將節(jié)點進行分簇，且每個普通節(jié)點完成分簇后，更新簇頭節(jié)點的能耗值。

3 實驗結(jié)果

為驗證本文算法的有效性和先進性，選擇了目前針對異構(gòu)無線傳感器網(wǎng)絡(luò)優(yōu)化效果較好的GLBCA、GA和GAR等算法，在不同基站位置、布撒不同比例的普通節(jié)點和高能節(jié)點等情況下進行對比驗證本文算法的性能。實驗中的相關(guān)參數(shù)如表3所示。三個算法中的參數(shù)采用相關(guān)文獻給出的數(shù)值進行設(shè)置。每組實驗保證初始的節(jié)點布撒場景相同。

表3 參數(shù)設(shè)置

3.1 路由算法有效性驗證

為驗證本文提出的基于差分的路由算法的有效性，分別與GLBCA、GA和GAR進行對比，具體如圖1所示。其中，圖1為基站位置在(250,250)時，向網(wǎng)絡(luò)中布撒50個高能節(jié)點時，四種算法得到的拓?fù)浣Y(jié)構(gòu)。

(a) DE (b) GLBCA

(c) GA (d) GAR

從圖1中可以看出，DE、GLBCA、GA和GAR四種算法優(yōu)化網(wǎng)絡(luò)得到的拓?fù)浣Y(jié)構(gòu)差異較大。因為簇頭節(jié)點更靠近基站，所以會接收和轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)信息給基站，而接收轉(zhuǎn)發(fā)信息會消耗一定的能量，因此，靠近基站的簇頭將會率先耗盡自身的能量，也即每條通信鏈路上含有的節(jié)點數(shù)目越少，則靠近基站的簇頭的生存周期越長。從圖中可以看出DE算法得到的網(wǎng)絡(luò)中最長通信鏈路上的簇頭數(shù)為9個，GLBCA的最大通信鏈路上的簇頭數(shù)為16個，GA為14個，GAR為14個。也即DE算法優(yōu)化的網(wǎng)絡(luò)中，靠近基站的簇頭能耗更低，因此具備更長的網(wǎng)絡(luò)生存周期。

3.2 路由分簇算法性能對比

通過對比不同基站位置、不同普通節(jié)點數(shù)和不同高能節(jié)點數(shù)目下， 驗證DE、GLBCA、GA和GAR的算法性能。表4、表5是在基站位置在 (250,250)時，分別布撒20和50高能節(jié)點，普通節(jié)點數(shù)目在200～500之間各個算法獲得網(wǎng)絡(luò)生命周期的對比情況。表6、表7是在基站位置在(250,500)時，分別布撒20和50高能節(jié)點，普通節(jié)點數(shù)目在200～500之間各個算法的對比情況。

表4 基站在(250,250)，簇頭數(shù)為20不同算法性能對比

表5 基站在(250,250)時，簇頭數(shù)為50不同算法性能對比

表6 基站在(250,500)，簇頭數(shù)為20不同算法性能對比

表7 基站在(250,500)，簇頭數(shù)為50不同算法性能對比

從表4-表7可以看出：

1) 隨節(jié)點數(shù)目的增多，四種算法優(yōu)化的網(wǎng)絡(luò)生存周期都逐漸下降，這是因為節(jié)點數(shù)目的增加，簇頭節(jié)點接收融合信息的能耗也隨之增加；

2) 當(dāng)基站位置及普通節(jié)點的數(shù)目相同時，布撒50路由節(jié)點的能耗高于布撒20路由節(jié)點，這是因為實驗中假設(shè)不論本簇內(nèi)含有普通節(jié)點的數(shù)目是多少，每個路由節(jié)點發(fā)送融合后的數(shù)據(jù)包大小相同；

3) 當(dāng)基站位置不同、路由節(jié)點數(shù)不同或普通節(jié)點數(shù)不同時，基于差分的分簇路由協(xié)議與其他三種算法相比有著明顯的優(yōu)勢，也即能得到生存周期更長的異構(gòu)網(wǎng)絡(luò)。

綜上說明，在不同基站位置、不同路由節(jié)點和普通節(jié)點布撒數(shù)目的情況下，本文算法在優(yōu)化異構(gòu)無線傳感器網(wǎng)絡(luò)時，都能更好地延長網(wǎng)絡(luò)整體的工作時間。

4 結(jié) 語

針對異構(gòu)傳感器網(wǎng)絡(luò)中的能耗不均問題，本文提出一種基于差分進化算法的路由算法和基于節(jié)點能耗的分簇算法。首先以網(wǎng)絡(luò)中簇頭節(jié)點的最短生存周期為目標(biāo)，采用差分算法對其進行優(yōu)化，降低了通信中各個簇頭節(jié)點的能耗差異，然后根據(jù)節(jié)點與簇頭的距離、網(wǎng)絡(luò)中簇頭節(jié)點的負(fù)載壓力以及兩種節(jié)點的能量差異對各個節(jié)點進行分簇，使簇頭和節(jié)點的壽命都盡可能達到最大。實驗仿真表明，本文算法在不同節(jié)點數(shù)目以及不同的環(huán)境下，均能使整個網(wǎng)絡(luò)的生存周期達到最大，驗證了本文算法的有效性及先進性。

[1] Chong C Y, Kumar S P. Sensor networks: evolution, opportunities, and challenges[J].Proceedings of the IEEE, 2003, 91(8):1247-1256.

[2] Abbasi A A, Younis M. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications, 2007,30(14-15):2826-2841.

[3] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocols for wireless microsensor networks[C]//Proceedings of the Hawaaian International Conference on Systems Sciences, Hawaii,2000:3005-3014.

[4] 余勇昌, 韋崗. 無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法[J].電子學(xué)報,2008,36(7):1309-1313.

[5] Tang J, Hao B, Sen A. Relay node placement in large scale wireless sensor networks[J].Computer Communications,2006,29(4):490-501.

[6] 孫力娟, 魏靜, 郭劍,等.面向異構(gòu)無線傳感器網(wǎng)絡(luò)的節(jié)點調(diào)度算法[J].電子學(xué)報,2014,42(10):1907-1912.

[7] Low C P, Fang C, Ng J M, et al. Efficient Load-Balanced Clustering Algorithms for wireless sensor networks[J].Computer Communications,2008,31(4):750-759.

[8] Gupta S K, Jana P K. Energy Efficient Clustering and Routing Algorithms for Wireless Sensor Networks: GA Based Approach[J].Wireless Personal Communications, 2015,83(3):2403-2423.

[9] Gupta S K, Kuila P, Jana P K. GAR: An Energy Efficient GA-Based Routing for Wireless Sensor Networks[C]//9th International Conference on Distributed Computing and Internet Technologies, 2013:267-277.

[10] Heinzelman W B, Chandrakasan A P, Balakrishnan H. Application-specific protocol architectures for wireless networks[D].Cambridge, MA, USA: Massachusetts Institute of Technology,2000.

ROUTING CLUSTERING PROTOCOL FOR WIRELESS SENSOR NETWORKS BASED ON DIFFERENCE ALGORITHM

Li Zhiming Tang Yongzhong

(CenterforInformationTechnology,HexiUniversity,Zhangye734000，Gansu，China)

Aiming at the problem of node energy consumption imbalance in heterogeneous wireless sensor networks, a routing protocol based on differential evolution algorithm and a clustering protocol based on node energy consumption are proposed. The protocol first aims at maximizing the minimum lifetime of cluster head nodes in the network to establish the function optimization model, and uses differential evolution algorithm to optimize it to extend the whole life cycle of the network. Then, the nodes are clustered according to the number of cluster heads in the node communication list, and the nodes are allocated to the cluster head with lower energy consumption, so as to balance the energy consumption of the network and extend the life cycle of the common nodes. The simulation results show that the difference-based routing clustering protocol can effectively balance the energy consumption of nodes in the network, extend the life cycle of the network and improve the network energy efficiency.

Heterogeneous wireless sensor networks Routing Clustering Difference algorithm

2016-05-31。李志明，講師，主研領(lǐng)域：圖像處理，計算機網(wǎng)絡(luò)應(yīng)用。唐永中，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.01.024