移動(dòng)無線傳感器網(wǎng)絡(luò)中分布式重聚類算法研究

徐超杰, 俞　暉, 羅漢文

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

?

移動(dòng)無線傳感器網(wǎng)絡(luò)中分布式重聚類算法研究

徐超杰, 俞暉, 羅漢文

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

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

關(guān)鍵詞:移動(dòng)無線傳感器網(wǎng)絡(luò); 聚類; 分布式; 重聚類; 數(shù)據(jù)送達(dá)率; 能耗

0概述

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

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

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

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

1系統(tǒng)模型

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

1.1節(jié)點(diǎn)移動(dòng)模型

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

(1)

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

(2)

其中,(xk-1,yk-1)為節(jié)點(diǎn)在時(shí)刻k-1時(shí)的位置,t為每個(gè)時(shí)間間隔的固定長(zhǎng)度.

為了獲得更加真實(shí)的移動(dòng)模型,對(duì)Gauss-Markov移動(dòng)模型進(jìn)行了限定,即限定節(jié)點(diǎn)運(yùn)動(dòng)速度在一定范圍內(nèi)變化,相鄰時(shí)間間隔內(nèi)節(jié)點(diǎn)運(yùn)動(dòng)方向變化也限定在一定范圍內(nèi).

1.2能耗模型

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

(3)

其中,εelec為發(fā)送端發(fā)送每比特?cái)?shù)據(jù)所消耗能量;εfs為自由空間信道模型下放大每比特?cái)?shù)據(jù)所消耗能量,εmp為多徑衰落信道模型下對(duì)應(yīng)消耗能量;d0為臨界距離值,其計(jì)算為:

(4)

接收端接收l比特?cái)?shù)據(jù)所消耗能量計(jì)算為:

(5)

2分布式重聚類算法

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

2.1節(jié)點(diǎn)位置估計(jì)

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

(6)

其中,pk=(xk,yk)與?k分別為節(jié)點(diǎn)在時(shí)刻k的位置與運(yùn)動(dòng)方向.根據(jù)航跡推算法,sk的更新模型為:

(7)

其中,vk-1與?k-1分別為節(jié)點(diǎn)在時(shí)間間隔k-1的運(yùn)動(dòng)速度與方向;Δ?k為從時(shí)間間隔k-1到時(shí)間間隔k過程中節(jié)點(diǎn)運(yùn)動(dòng)方向的變化;t為每個(gè)時(shí)間間隔的固定值.

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(3) 重采樣階段:為了避免所有的權(quán)重值集中于某些粒子而導(dǎo)致目標(biāo)空間不能很好覆蓋,對(duì)具有較低權(quán)重值的粒子進(jìn)行重采樣.在時(shí)刻k,定義粒子的有效數(shù)目為:

(15)

(4) 預(yù)測(cè)階段:在時(shí)刻k,節(jié)點(diǎn)的狀態(tài)為

(16)

2.2節(jié)點(diǎn)位置預(yù)測(cè)

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

圖1　節(jié)點(diǎn)位置預(yù)測(cè)中可能位置示意圖

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

(17)

2.3分布式重聚類過程

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

(18)

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

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

3仿真結(jié)果與分析

本文作者提出了一種移動(dòng)無線傳感器網(wǎng)絡(luò)中的分布式重聚類算法,為了評(píng)價(jià)該算法的效果,本文作者利用Matlab平臺(tái)進(jìn)行了仿真實(shí)驗(yàn).在本節(jié)中,該分布式重聚類算法簡(jiǎn)稱為DRC算法.仿真實(shí)驗(yàn)中主要仿真參數(shù)設(shè)置如表1所示.

表1　主要仿真參數(shù)設(shè)置

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

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

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

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

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

圖3　數(shù)據(jù)送達(dá)率累積分布函數(shù)曲線對(duì)比

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

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

4結(jié)束語

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

參考文獻(xiàn):

[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.

(責(zé)任編輯：顧浩然)

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

中圖分類號(hào):TN 929.5

文獻(xiàn)標(biāo)志碼:A

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

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

收稿日期:2016-03-04