何杏宇，楊桂松，周亦敏

(1.上海理工大學(xué) 實(shí)驗(yàn)室管理與服務(wù)中心，上海200093;2.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

0 引 言

無線傳感器節(jié)點(diǎn)的能量限制一直以來是無線傳感器網(wǎng)絡(luò)應(yīng)用中的瓶頸問題。為了避免因網(wǎng)絡(luò)中能量消耗不均而導(dǎo)致的網(wǎng)絡(luò)不穩(wěn)定，一些層次型協(xié)議相繼提出。LEACH［1］算法是較早提出的層次型算法，該算法以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，使得網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡。隨后，研究人員對LEACH 算法進(jìn)行了各種改進(jìn)，其中，HEED［2］算法要求在節(jié)點(diǎn)選取簇頭時(shí)考慮其剩余能量。同樣，文獻(xiàn)［3，4］也基于節(jié)點(diǎn)剩余能量對LEACH 算法提出了改進(jìn)。而文獻(xiàn)［5，6］提出了基于節(jié)點(diǎn)密度的簇型算法，進(jìn)一步提高網(wǎng)絡(luò)能量均衡。文獻(xiàn)［7，8］則對近年來關(guān)于LEACH 的改進(jìn)算法進(jìn)行了總結(jié)和比較。然而，這些算法中均未考慮到簇頭節(jié)點(diǎn)和簇成員之間的通信代價(jià)均衡問題，以及是否存在“孤立簇頭”的問題。

為此，本文提出了一種基于作用力模型的移動(dòng)簇型協(xié)議，該算法基于節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密度進(jìn)行輪換簇頭選舉，簇頭節(jié)點(diǎn)能夠根據(jù)基于簇成員剩余能量和距離的作用力模型進(jìn)行自適應(yīng)移動(dòng)，以均衡簇頭和簇成員之間的通信代價(jià)，另外，本文還提出了基于節(jié)點(diǎn)剩余能量的中繼節(jié)點(diǎn)選舉算法，以在簇頭之間形成可連通的且有利于均衡的主干路徑。

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

本文定義的網(wǎng)絡(luò)模型為:1)網(wǎng)絡(luò)中的節(jié)點(diǎn)結(jié)構(gòu)和初始能量相同，且能量不可補(bǔ)給，在部署后具有可移動(dòng)性和獲知其位置信息的能力;2)采用文獻(xiàn)［9］中的無線通信能量計(jì)算模型。

2 基于作用力模型的移動(dòng)簇型協(xié)議

本協(xié)議包括簇的建立階段和主干路徑建立階段。

2.1 簇的建立階段

2.1.1 簇頭選舉

本文提出基于節(jié)點(diǎn)鄰居密度和節(jié)點(diǎn)剩余能量的簇頭選舉算法:每個(gè)節(jié)點(diǎn)產(chǎn)生［0，1］之間的一個(gè)隨機(jī)數(shù)，若隨機(jī)數(shù)小于閾值T(n)，則該節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)，為了讓剩余能量較多的節(jié)點(diǎn)成為簇頭，且加大節(jié)點(diǎn)密集區(qū)域中簇頭節(jié)點(diǎn)的數(shù)量，T(n)的計(jì)算公式為

其中，Eresidual為節(jié)點(diǎn)的剩余能量，Eaverage為節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的平均剩余能量，如果節(jié)點(diǎn)的剩余能量大于鄰居節(jié)點(diǎn)的平均能量則成為簇頭節(jié)點(diǎn)的概率增大，反之，減小;1/p 為網(wǎng)絡(luò)節(jié)點(diǎn)中簇頭比例為p 時(shí)每個(gè)簇包含的節(jié)點(diǎn)數(shù)量，Nneigbor為鄰居節(jié)點(diǎn)數(shù)量，N 為網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)量，當(dāng)鄰居節(jié)點(diǎn)數(shù)量比1/p 多時(shí)，該區(qū)域簇頭節(jié)點(diǎn)數(shù)量增加，反之，減少。

2.1.2 簇頭節(jié)點(diǎn)的自適應(yīng)移動(dòng)

在簇頭選舉后和簇頭節(jié)點(diǎn)進(jìn)行自適應(yīng)移動(dòng)之前，應(yīng)先獲取簇頭節(jié)點(diǎn)移向的位置。為此，本文提出一個(gè)與距離和剩余能量相關(guān)的作用力模型，該模型設(shè)簇頭節(jié)點(diǎn)最終移向的位置為目標(biāo)點(diǎn)，假定q 個(gè)簇成員節(jié)點(diǎn)將在與簇頭節(jié)點(diǎn)連線方向上分別產(chǎn)生q 個(gè)牽引力，牽引力大小與其剩余能量和其與簇頭之間的距離相關(guān)，第i 個(gè)簇成員產(chǎn)生的牽引力fi的計(jì)算公式為

其中，α，β 為權(quán)重系數(shù)，Li為第i 個(gè)簇成員節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間的距離，Ei為第i 個(gè)簇成員的剩余能量。這q 個(gè)簇成員對簇頭分別產(chǎn)生q 個(gè)牽引力，距離簇頭越遠(yuǎn)的節(jié)點(diǎn)產(chǎn)生的牽引力越大，反之，越小;剩余能量越小的節(jié)點(diǎn)產(chǎn)生的牽引力越大，反之，越小。該模型由勢能最小原理(一個(gè)力學(xué)系統(tǒng)處于平衡狀態(tài)時(shí)勢能最小)要求這q 個(gè)簇成員在目標(biāo)點(diǎn)位置所產(chǎn)生的多個(gè)牽引力的合力為0。

下面將以q=3 為例對利用作用力模型對目標(biāo)點(diǎn)的位置求解進(jìn)行簡化說明。如圖1 所示，原xy 坐標(biāo)系以簇頭為原點(diǎn)，其坐標(biāo)為(X，Y)=(0，0)簇頭節(jié)點(diǎn)接收到的3 個(gè)簇成員節(jié)點(diǎn)在原xy 坐標(biāo)系中的坐標(biāo)分別為(X1，Y1)，(X2，Y2)和(X3，T3)，設(shè)目標(biāo)點(diǎn)的坐標(biāo)為(X0，Y0)。

圖1 簇成員和目標(biāo)點(diǎn)的位置關(guān)系Fig 1 Location relationship between cluster members and target point

首先，將簇頭節(jié)點(diǎn)和三個(gè)簇成員節(jié)點(diǎn)的坐標(biāo)轉(zhuǎn)換至以目標(biāo)點(diǎn)為原點(diǎn)的(X'，Y')坐標(biāo)系中。轉(zhuǎn)換后的目標(biāo)點(diǎn)坐標(biāo)為(X'0，Y'0)，(X'0，Y'0)=((X0－X0)，(Y0－Y0))=(0，0)，而三個(gè)簇成員節(jié)點(diǎn)的坐標(biāo)的計(jì)算公式分別為

然后，根據(jù)三個(gè)簇成員和目標(biāo)點(diǎn)的位置關(guān)系和剩余能量可以獲得以目標(biāo)點(diǎn)為原點(diǎn)的作用力模型如圖2 所示:三個(gè)簇成員產(chǎn)生的牽引力矢量坐標(biāo)分別為

圖2 作用力模型Fig 2 Force model

由式(4)可推導(dǎo)出

由于在目標(biāo)點(diǎn)位置三個(gè)簇成員節(jié)點(diǎn)產(chǎn)生的三個(gè)牽引力f1，f2，f3對應(yīng)的矢量和為0，亦即，X″1+X″2+X″3=0，Y″1+Y″2+Y″3=0，則可以推算出

根據(jù)式(5)，進(jìn)而可以推算出

當(dāng)q=3 時(shí)，目標(biāo)點(diǎn)的計(jì)算公式為

對上述模型進(jìn)行推廣，當(dāng)簇頭節(jié)點(diǎn)接收到q 個(gè)簇成員的節(jié)點(diǎn)的坐標(biāo)信息分別為(Xi，Yi)，i=1 ～q 時(shí)，則此時(shí)目標(biāo)點(diǎn)的坐標(biāo)計(jì)算公式為

2.2 主干路徑建立階段

在簇頭自適應(yīng)移動(dòng)后，為了在簇頭節(jié)點(diǎn)之間建立全連通的主干路徑，本文提出如圖3 所示的基于通信半徑和剩余能量的中繼節(jié)點(diǎn)選舉算法。當(dāng)存在“孤立簇頭”時(shí)，便可按照圖3 所示算法進(jìn)行中繼節(jié)點(diǎn)選舉。

圖3 中繼節(jié)點(diǎn)選舉算法流程圖Fig 3 Flow chart of relay node election algorithm

設(shè)定V 為判斷簇成員成為中繼節(jié)點(diǎn)的可能性大小的參數(shù)，V 的計(jì)算公式為

其中，θ 和μ 為權(quán)重系數(shù)，Eresidual為簇成員的剩余能量大小，L1為簇成員到發(fā)起中繼請求的簇頭的距離，L2為簇成員到對接簇頭的距離。由式(11)可知，當(dāng)簇成員的剩余能量越高，其成為中繼節(jié)點(diǎn)的可能性越高，反之，越低;簇成員到中繼請求節(jié)點(diǎn)和對接簇頭的距離和越小，其成為中繼節(jié)點(diǎn)的可能性越高，反之，越低。

3 仿真與實(shí)驗(yàn)

本文使用NS2 平臺對文獻(xiàn)［5］所提出的基于節(jié)點(diǎn)剩余能量的LEACH—E 協(xié)議、文獻(xiàn)［6］所提出的基于節(jié)點(diǎn)密度的LEACH—D 協(xié)議以及本文提出的算法分別進(jìn)行了仿真，并對這三種協(xié)議的仿真結(jié)果進(jìn)行了對比分析。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文的仿真場景為400 個(gè)節(jié)點(diǎn)隨機(jī)部署在一個(gè)200 m×200 m 的正方形區(qū)域內(nèi)，其Sink 節(jié)點(diǎn)位于正方形的中心。仿真參數(shù)如表1 所示。

表1 仿真參數(shù)Tab 1 Simulation parameters

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

由圖4 可知，LEACH—E 和LEACH—D 協(xié)議都有具有最高的能耗方差且波動(dòng)較大，從而反映出較大的網(wǎng)絡(luò)能耗不均衡性。相較之下，本文提出的協(xié)議有效地降低了方差，呈現(xiàn)出較好的能耗均衡狀況。

圖4 節(jié)點(diǎn)能量消耗方差Fig 4 Energy consumption variance of nodes

由圖5 可知，LEACH—E 由于考慮到節(jié)點(diǎn)的剩余能量，在網(wǎng)絡(luò)運(yùn)行初期節(jié)點(diǎn)死亡數(shù)量比LEACH—D 協(xié)議少，但隨著網(wǎng)絡(luò)的運(yùn)行時(shí)間推移，反映出沒有考慮節(jié)點(diǎn)密度的缺陷，節(jié)點(diǎn)死亡率反而比LEACH—D 協(xié)議高;相較之下，本文提出的協(xié)議兼顧了節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密度，并采用了簇頭自適應(yīng)移動(dòng)策略，使得網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗均衡性進(jìn)一步提高，節(jié)點(diǎn)的使用壽命趨于一致，大部分節(jié)點(diǎn)都堅(jiān)持到網(wǎng)絡(luò)剩余周期的末期才死亡。

4 結(jié) 論

圖5 節(jié)點(diǎn)存活的個(gè)數(shù)Fig 5 Number of alive nodes

本文提出的基于作用力模型的移動(dòng)簇型協(xié)議在進(jìn)行簇頭選舉時(shí)提高了剩余能量大的節(jié)點(diǎn)成為簇頭的概率，同時(shí)增加了節(jié)點(diǎn)密度較大區(qū)域簇頭節(jié)點(diǎn)的個(gè)數(shù)，該算法允許簇頭節(jié)點(diǎn)基于簇成員剩余能量和距離的牽引力作用下進(jìn)行自適應(yīng)移動(dòng)，均衡了簇頭和簇成員之間的通信代價(jià)。同時(shí)，本文提出的中繼節(jié)點(diǎn)選舉算法，實(shí)現(xiàn)了簇頭節(jié)點(diǎn)之間的全連通。實(shí)驗(yàn)結(jié)果證明:本文提出的協(xié)議能夠有效地均衡網(wǎng)絡(luò)能耗，顯著地延長網(wǎng)絡(luò)的生命周期。

［1］ Heinzelan W R，Chandrakasan A，Balakrishnan H.An application－specific protocol architecture for wireless micro sensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［2］ Youni O，F(xiàn)ahmy S.HEED:A hybrid，energy－efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366－379.

［3］ 龔本燦，蔣廷耀，汪祥莉.一種基于剩余能量的無線傳感器網(wǎng)絡(luò)分簇協(xié)議［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(8):31－33.

［4］ Peng D，Zhang Q.An energy efficient cluster－routing protocol for wireless sensor networks［C］∥International Conference on Computer Design and Applications，Qinghuangdao:IEEE，2010:530－533.

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

［6］ 路成杰，蔣海峰.一種基于節(jié)點(diǎn)密度的無線傳感器網(wǎng)絡(luò)協(xié)議［J］.傳感器與微系統(tǒng)，2014，33(9):114－116.

［7］ Li Y，Zhang A，Liang Y.Improvement of leach protocol for wireless sensor networks［C］∥The third International Conference on Instrumentation，Measurement，Computer，Communication and Control，Shenyang:IEEE，2013:322－326.

［8］ Keert N，Anand G.Improved cluster routing protocol for wireless sensor networks through simplification［C］∥18th Annual International Conference on Advanced Computing and Communications，Bangalore:IEEE，2012:1－3.

［9］ Su I，Tsai C，Sung W.Area temperature system monitoring and computing based on adaptive fuzzy logic in wireless sensor networks［J］.Applied Soft Computing，2012，12(5):1532－1541.