徐超杰, 俞　暉, 羅漢文

(上海交通大學 電子信息與電氣工程學院,上海 200240)

?

移動無線傳感器網絡中分布式重聚類算法研究

徐超杰, 俞暉, 羅漢文

(上海交通大學 電子信息與電氣工程學院,上海 200240)

摘要:移動無線傳感器網絡中,節(jié)點的移動性影響著層次化聚類之后的網絡結構,從而影響聚類內部節(jié)點間通信時的數據送達率與能耗.為了降低節(jié)點移動性的影響,本文提出了一種分布式重聚類算法.該算法基于已聚類網絡,利用粒子濾波算法對節(jié)點當前位置進行估計,并結合移動模型預測下一時刻位置;處于聚類邊界的非簇頭節(jié)點周期性地評估自身是否需要重聚類,并在需要時通過與所屬聚類及目標聚類的簇頭節(jié)點通信,將自身重聚類到目標聚類中.仿真結果表明,在重聚類周期較小時,該算法能夠使節(jié)點在移動過程中保持合理的通信距離,并在數據送達率與能耗方面優(yōu)于現有的算法.

關鍵詞:移動無線傳感器網絡; 聚類; 分布式; 重聚類; 數據送達率; 能耗

0概述

移動無線傳感器網絡由大量移動節(jié)點組成,這些節(jié)點被布置于目標區(qū)域中以完成諸如目標跟蹤與環(huán)境條件監(jiān)測等任務.節(jié)點將采集到的數據發(fā)送至匯聚節(jié)點或者服務器進行處理,由于節(jié)點能量有限,為了延長網絡的生命周期,必須對節(jié)點進行高效利用[1-2].

在無線傳感器網絡中,層次化聚類方法有利于降低網絡能耗與提高數據發(fā)送效率等.文獻[3]提出的LEACH是一種自適應的聚類算法,一些節(jié)點被隨機地選為簇頭,其他節(jié)點加入到距其最近的簇頭節(jié)點形成聚類,該算法周期性地對簇頭節(jié)點進行輪轉以平衡節(jié)點之間能量消耗差異.文獻[4]提出了一種分布式聚類算法,通過迭代過程實現聚類與簇頭節(jié)點的選取,該算法根據節(jié)點的剩余能量對簇頭節(jié)點進行輪轉.考慮到節(jié)點的移動性,文獻[5]提出了LEACH-mobile算法,該算法要求移動節(jié)點在移動時對所屬聚類進行聲明.

在已聚類的移動無線傳感器網絡中,節(jié)點的移動性隨機、動態(tài)地影響著網絡的拓撲結構,使得節(jié)點未處于合適的聚類中,非簇頭節(jié)點與簇頭節(jié)點之間的通信距離增加,導致通信能耗增加、數據送達率降低[6],降低了網絡的服務質量.因此需要重聚類過程,使節(jié)點加入到合適的聚類中.在已有的聚類協(xié)議中,重聚類算法主要分為集中式重聚類算法與分布式重聚類算法.在集中式重聚類算法中,重聚類過程由簇頭節(jié)點或匯聚節(jié)點控制,非簇頭節(jié)點處于從屬地位,并且重聚類主要目的是輪轉簇頭節(jié)點,非簇頭節(jié)點僅在簇頭節(jié)點輪轉時才能被重聚類.在分布式重聚類算法中,非簇頭節(jié)點可以評估自身是否需要重聚類,并在合適的時機進行重聚類.文獻[7]提出了一種集中式重聚類算法,將簇頭節(jié)點與匯聚節(jié)點控制的重聚類過程進行結合.文獻[8]提出的self-incentive and semi-reclustering(SISR)是一種分布式重聚類算法,該算法主要處理簇頭節(jié)點輪轉時導致的非簇頭節(jié)點重聚類問題,允許聚類邊界區(qū)域的非簇頭節(jié)點在必要時重聚類到更合適的聚類中.但是,SISR中重聚類過程僅在目標聚類下一次簇頭輪轉開始時才能進行,導致較長的重聚類周期.在大多數聚類協(xié)議中,節(jié)點的位置主要通過GPS或者其他定位方式獲得,這將引入較大的能耗,同時也使得這些協(xié)議在GPS等定位方式無法使用的場景中失效.

本文作者提出了一種分布式重聚類算法,該算法基于已聚類的移動無線傳感器網絡,利用粒子濾波算法結合慣性傳感器數據實現對節(jié)點當前時刻位置的估計,并根據節(jié)點移動模型預測節(jié)點下一時刻的位置;該算法允許處于聚類邊界區(qū)域的非簇頭節(jié)點對自身是否需要重聚類進行評估,并在必要時通過與所屬聚類及目標聚類的簇頭節(jié)點進行通信,自主地完成重聚類過程.

1系統(tǒng)模型

移動無線傳感器網絡由移動節(jié)點組成,初始時這些節(jié)點被隨機布置在目標區(qū)域中且初始位置已知,之后節(jié)點不能通過GPS或者其他類似定位方式獲取位置.在運動過程中,每個節(jié)點都可以獲得自身的運動速度與方向.本節(jié)主要介紹節(jié)點的移動模型以及節(jié)點之間通信時的能耗模型.

1.1節(jié)點移動模型

假設節(jié)點的運動遵從特定的移動模型.Gauss-Markov移動模型中[9],假定每個時間間隔中運動情況不變,時間間隔k(時刻k與時刻k+1之間)的運動情況與時間間隔k-1中運動情況相關,并能夠通過改變隨機度參數獲得不同隨機程度的移動模型,能夠很好地模擬節(jié)點的運動情況.時間間隔k中運動速度與方向的更新規(guī)則為:

(1)

初始時,每個節(jié)點都具有初始速度v0與方向d0;在時刻k,節(jié)點位置更新規(guī)則為:

(2)

其中,(xk-1,yk-1)為節(jié)點在時刻k-1時的位置,t為每個時間間隔的固定長度.

為了獲得更加真實的移動模型,對Gauss-Markov移動模型進行了限定,即限定節(jié)點運動速度在一定范圍內變化,相鄰時間間隔內節(jié)點運動方向變化也限定在一定范圍內.

1.2能耗模型

主要考慮節(jié)點之間通信時的能耗,根據發(fā)送端與接收端之間的距離,分別采用自由空間與多徑衰落信道模型.發(fā)送端將l比特數據發(fā)送到距離其d處接收端的能耗計算為:

(3)

其中,εelec為發(fā)送端發(fā)送每比特數據所消耗能量;εfs為自由空間信道模型下放大每比特數據所消耗能量,εmp為多徑衰落信道模型下對應消耗能量;d0為臨界距離值,其計算為:

(4)

接收端接收l比特數據所消耗能量計算為:

(5)

2分布式重聚類算法

本文作者提出的分布式重聚類算法基于已層次化聚類的移動無線傳感器網絡,主要包括節(jié)點利用粒子濾波算法[10]對當前自身位置進行估計,節(jié)點根據移動模型預測下一時刻自身位置,處于聚類邊界區(qū)域的非簇頭節(jié)點通過與所屬聚類的簇頭節(jié)點通信,對自身是否需要重聚類進行估計,并在需要重聚類時,通過與所屬聚類及目標聚類的簇頭節(jié)點進行通信,將自身重聚類到目標聚類中.

2.1節(jié)點位置估計

由于節(jié)點不能通過GPS或者其他定位方式來獲取自身的位置.采用粒子濾波算法對節(jié)點在每個時刻的位置進行估計.定義節(jié)點在時刻k的狀態(tài)為:

(6)

其中,pk=(xk,yk)與?k分別為節(jié)點在時刻k的位置與運動方向.根據航跡推算法,sk的更新模型為:

(7)

其中,vk-1與?k-1分別為節(jié)點在時間間隔k-1的運動速度與方向;Δ?k為從時間間隔k-1到時間間隔k過程中節(jié)點運動方向的變化;t為每個時間間隔的固定值.

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(3) 重采樣階段:為了避免所有的權重值集中于某些粒子而導致目標空間不能很好覆蓋,對具有較低權重值的粒子進行重采樣.在時刻k,定義粒子的有效數目為:

(15)

(4) 預測階段:在時刻k,節(jié)點的狀態(tài)為

(16)

2.2節(jié)點位置預測

結合節(jié)點在時間間隔k-1中的運動情況,節(jié)點移動模型中對節(jié)點運動速度及相鄰時間間隔中運動方向變化的限定,節(jié)點在時間間隔k的運動速度范圍與運動方向變化范圍可由公式(1)計算得到,分別表示為Vrange=[vmin,vmax]與Drange=[-θ1,θ2].因此在時刻k+1節(jié)點的可能位置被限定為圖1中扇形陰影區(qū)域.

圖1　節(jié)點位置預測中可能位置示意圖

Vrange中每個可能的速度值vi在公式(1)中均有對應的高斯隨機變量vxk-1,Drange中每個可能的運動方向變化值θj在公式(1)中也存在對應的高斯隨機變量dxk-1,因此vi與θj的概率值分別等于對應vxk-1與dxk-1出現的概率值.由于vxk-1與dxk-1相互獨立,vi與θj對應的節(jié)點可能位置sij出現的概率為p(sij)=p(vi)·p(θj).將Vrange與Drange中速度值與方向變化值進行離散化,計算每一對vi與θj對應可能位置sij的集合S以及對應的概率值p(sij)的集合P.從S中隨機選取Nrand個可能位置,這些可能位置對應的概率值集合為Prand,將Prand中概率值排序,并選擇概率值最高的Nsel個概率值為集合Psel,對應的可能位置組成集合Ssel.歸一化集合Psel中的概率值得到集合Pnorm,則根據Ssel中節(jié)點可能位置及其對應的歸一化概率值集合Pnorm可以計算節(jié)點在時刻k+1的預測位置:

(17)

2.3分布式重聚類過程

每個重聚類周期開始時,非簇頭節(jié)點將當前時刻自身的估計位置與下一時刻的預測位置發(fā)送給所屬聚類的簇頭節(jié)點,簇頭節(jié)點整合聚類內所有節(jié)點的位置數據后與鄰近聚類的簇頭節(jié)點交換位置數據,并將鄰近聚類及本聚類中節(jié)點的估計位置信息發(fā)送給聚類中處于邊界區(qū)域的非簇頭節(jié)點(簡稱邊界節(jié)點),邊界節(jié)點評估自身是否需要進行重聚類即計算對所屬聚類及各個鄰近聚類之間的從屬度.節(jié)點i對聚類C的從屬度計算定義為:

(18)

其中,d(i,j)為節(jié)點i與j之間的歐式距離.對于節(jié)點i,具有較大從屬度的聚類更適合其加入.邊界節(jié)點將具有最高從屬度的聚類作為當前時刻最適合其加入的聚類Cnow-opt,若Cnow-opt與當前所屬聚類Cnow不同,則說明當前時刻該邊界節(jié)點需要進行重聚類.

需要進行重聚類的邊界節(jié)點首先向Cnow的簇頭節(jié)點發(fā)送重聚類請求信息,Cnow的簇頭節(jié)點將Cnow中重聚類請求情況與鄰近聚類的簇頭節(jié)點進行交換,并將Cnow與鄰近聚類中節(jié)點的預測位置及重聚類請求情況發(fā)送給請求重聚類的邊界節(jié)點.該邊界節(jié)點再次進行重聚類評估,得到下一時刻最適合其加入的聚類Cnext-opt,若Cnext-opt與Cnow不同,即重聚類過程中不存在乒乓效應,該邊界節(jié)點能夠重聚類到聚類Cnow-opt中,否則當前重聚類過程不進行.若該邊界節(jié)點能夠進行重聚類,則向Cnow的簇頭節(jié)點發(fā)送重聚類確認信息,并向Cnow-opt的簇頭節(jié)點發(fā)送請求加入信息,在下一時刻脫離聚類Cnow并加入聚類Cnow-opt.另外,本文作者提出的分布式重聚類算法中實行簇頭節(jié)點輪轉機制,輪轉準則為節(jié)點的剩余能量以及節(jié)點在聚類中所處的位置.

3仿真結果與分析

本文作者提出了一種移動無線傳感器網絡中的分布式重聚類算法,為了評價該算法的效果,本文作者利用Matlab平臺進行了仿真實驗.在本節(jié)中,該分布式重聚類算法簡稱為DRC算法.仿真實驗中主要仿真參數設置如表1所示.

表1　主要仿真參數設置

本文作者對DRC算法在不同重聚類周期T(單位:時間間隔)條件下的性能進行了評估,并與文獻[8]中提出的SISR算法進行了對比,每次仿真實驗時長為1000個時間間隔,非簇頭節(jié)點在每個時刻向所屬聚類的簇頭節(jié)點發(fā)送長度為1000比特的采集數據.

圖2　節(jié)點之間平均通信距離累積分布函數

在已聚類的移動無線傳感器網絡中分別應用DRC算法(T=1,2,4,8,16)與SISR算法,統(tǒng)計每個時刻非簇頭節(jié)點與對應的簇頭節(jié)點之間的平均通信距離,圖2為節(jié)點之間平均通信距離的累積分布函數曲線對比.從圖2中可以看出,T=1時DRC算法對應的節(jié)點之間平均通信距離值最小,隨著T增加,節(jié)點之間平均通信距離增大;SISR算法相較于DRC算法(T=1,2,4,8,16),由于對節(jié)點的重聚類處理不及時,導致節(jié)點之間平均通信距離較大.

在仿真實驗中,利用公式(3)與公式(5)計算節(jié)點通信造成的能耗,并根據節(jié)點之間的通信距離對數據送達率[6]進行計算.DRC算法(T=1,2,4,8,16)與SISR算法關于平均數據送達率的累積分布函數曲線對比如圖3所示.結合圖2與圖3可以看出,隨著T增加,節(jié)點之間平均數據送達率降低,節(jié)點之間通信距離的增加導致了節(jié)點之間數據送達率的降低.相比SISR算法,DRC算法(T=1,2,4,8,16)能夠使節(jié)點之間通信時保持更高的數據送達率.

圖4為DRC算法(T=1,2,4,8,16)與SISR算法對應的節(jié)點平均剩余能量變化曲線對比.從圖4中可以看出,隨著T從1增大到8,DRC算法對應的節(jié)點剩余能量變化速度逐漸減緩,說明隨著T增大,重聚類通信次數減少,其引起的能耗降低;然而在T=16時,節(jié)點剩余能量變化速度與T=4時相當,說明節(jié)點之間通信距離較大導致了節(jié)點之間單次通信耗能增加;而SISR算法由于節(jié)點之間通信距離過大,導致其對應的節(jié)點通信能耗較大.因此相比SISR算法,DRC算法(T=1,2,4,8,16)能耗較低.

圖3　數據送達率累積分布函數曲線對比

圖4　節(jié)點平均剩余能量變化曲線對比圖

通過仿真實驗可以看出,在T取值較小(如T=1,2,4,8,16)時,即對節(jié)點重聚類請求的處理較為及時的情況下,DRC算法在數據送達率及能耗方面的性能優(yōu)于SISR算法.

4結束語

為了解決移動無線傳感器網絡中節(jié)點移動性引起的重聚類問題,本文作者提出了一種分布式重聚類算法.該算法基于已聚類的移動無線傳感器網絡,利用粒子濾波算法結合慣性傳感器數據實現對節(jié)點當前時刻位置的估計,并根據節(jié)點移動模型預測下一時刻節(jié)點的位置;該算法允許處于聚類邊界區(qū)域的非簇頭節(jié)點對自身是否需要重聚類進行評估,并在必要時自主地完成重聚類過程;該算法還考慮了節(jié)點重聚類過程中的乒乓效應.仿真結果表明,在重聚類周期較小時,該算法在數據送達率與能耗方面的性能優(yōu)于現有算法.

參考文獻:

[1]Sayyed A,Becker L B.A survey on data collection in mobile wireless sensor networks (MWSNs) [M]//Koubaa A,Dios J R M.Cooperative Robots and Sensor Networks.Berlin:Springer,2015.

[2]Zhao M,Yanf Y,Wang C.Mobile data gathering with load balanced clustering and dual data uploading in wireless sensor networks [J].IEEE Transaction on Mobile Computing,2015,14(4):770-785.

[3]Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks [C]// IEEE.IEEE the 33rd annual Hawaii international conference on System sciences.Hawaii:IEEE,2000.

[4]Younis O,Fahmy S.Heed:A hybrid,energy-efficient,distributed clustering approach for ad hoc sensor networks [J].IEEE Transaction on Mobile Computing,2004,3(4):366-379.

[5]Kim D S,Chung G Y J.Self-organization routing protocol supporting mobile nodes for wire-less sensor network [C]//IEEE.IEEE First International Multi-Symposiums on Computer and Computational Sciences.Hangzhou:IEEE,2006.

[6]Zubiga M,Krishnamachari B.Analyzing the transitional region in low power wireless links [C]//IEEE.IEEE First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.Santa Clara:IEEE,2004:517-526.

[7]Guanathillake A,Samarasinghe K.Energy efficient clustering algorithm with global & local re-clustering for wireless sensor networks [J].World Academy of Science,Engineering and Technology,2013,7(7):45-52.

[8]Baek J,An S K,Fisher P.Dynamic cluster header selection and conditional re-clustering for wireless sensor networks [J].IEEE TransactionOnConsumer Electronics,2010,56(4):2249-2257.

[9]Mwila M K,Djouani K,Kurien A.An efficient approach to node localisation and tracking in wireless sensor networks [C]//IEEE.IEEE Global Communications Conference (GLOBECOM).Austin:IEEE,2014.

[10]Jing W,Zhao H,Lin X,et al.Selectively iterative particlefiltering and its applications for target tracking in WSNs [C]//IEEE.IEEE GlobalCommunications Conference (GLOBECOM).Atlanta:IEEE,2013.

(責任編輯：顧浩然)

Study on distributed re-clustering algorithm formoblie wireless sensor networks

XU Chaojie, YU Hui, LUO Hanwen

(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

Abstract:In mobile wireless sensor networks,node mobility influences the topology of the hierarchically clustered network,thus affects packet delivery ratio and energy consumption of communications in clusters.To reduce the influence of node mobility,a distributed re-clustering algorithm is proposed in this paper.In this algorithm,basing on the clustered network,nodes estimate their current locations with particle algorithm and predict the most possible locations of next time basing on the mobility model.Each boundary node of a cluster periodically estimates the need for re-clustering and re-cluster itself to the optimal cluster through communicating with the cluster headers when needed.The simulation results indicate that,with small re-clustering periods,the proposed algorithm can be effective to keep appropriate communication distance and outperforms existing schemes on packet delivery ratio and energy consumption.

Key words:mobile wireless sensor networks; cluster; distributed; re-clustering; packet delivery ratio; energy consumption

中圖分類號:TN 929.5

文獻標志碼:A

文章編號:1000-5137(2016)02-0202-07

通信作者:俞暉,中國上海市閔行區(qū)東川路800號,上海交通大學電子信息與電氣工程學院,郵編:200240,E-mail:yuhui@sjtu.edu.cn.

收稿日期:2016-03-04