基于移動預(yù)測的海上無線傳感網(wǎng)絡(luò)分簇算法

周 倩 張 琳

（上海海事大學(xué)，中國 上海 201306）

1 系統(tǒng)模型

1.1 基于移動模型的節(jié)點(diǎn)動態(tài)預(yù)測

海上無線傳感器網(wǎng)絡(luò)，節(jié)點(diǎn)呈現(xiàn)高度的動態(tài)性。為此，采用移動模型對節(jié)點(diǎn)狀態(tài)進(jìn)行模擬，移動模型是對網(wǎng)絡(luò)中移動節(jié)點(diǎn)移動方式的抽象，反應(yīng)了移動節(jié)點(diǎn)的位置、速度、加速度的變化情況。在現(xiàn)有的研究中，移動模型又有不同的分類方式，根據(jù)移動模型的構(gòu)建方式不同，移動模型分成蹤跡移動模型(Trace Mobility Model，TMM)與合成移動模型(Synthetic Mobility Model，SMM)兩類[4]。針對海上環(huán)境的特點(diǎn)，假設(shè)分布在海上的無線傳感器節(jié)點(diǎn)的運(yùn)動趨勢是基本一致的，將組移動模型應(yīng)用到無線傳感器網(wǎng)絡(luò)拓?fù)渲?，充分考慮節(jié)點(diǎn)間的位置關(guān)系，適當(dāng)刪除冗余鏈路，構(gòu)建合理拓?fù)洹?/p>

在這個模型中，節(jié)點(diǎn)運(yùn)動呈現(xiàn)一致性，具有一個相同的基礎(chǔ)速率和基礎(chǔ)移動方向，為了表示各節(jié)點(diǎn)移動狀態(tài)的差異性，各個節(jié)點(diǎn)的移動速率是由組移動速率加上隨機(jī)附加速率。

根據(jù)節(jié)點(diǎn)的運(yùn)動狀態(tài)對節(jié)點(diǎn)未來的移動狀態(tài)進(jìn)行預(yù)測，假設(shè)t 時刻得到節(jié)點(diǎn)的移動速率為v（t），移動方位為Φ（t），預(yù)測得到的t 時刻節(jié)點(diǎn)的移動速率為v1（t），移動方位為Φ1（t），預(yù)測t+1 時刻節(jié)點(diǎn)的移動速率為v2(t)，移動方位為Φ2（t），它們之間存在如下遞推關(guān)系：v2（t）＝(1-α)v1（t）+αv（t），v2（t）＝(1-β）Φ1（t）+βΦ（t）。

根據(jù)上述遞推公式，可以在t 時刻根據(jù)得到的移動目標(biāo)的運(yùn)動速率和方位以及歷史的預(yù)測結(jié)果預(yù)測出節(jié)點(diǎn)在t+1 時刻的運(yùn)動速率。

2 改進(jìn)的分簇協(xié)議

本文采用[1]中所提到的無線電傳播模型，根據(jù)無線信號傳播能量損耗模型可知，當(dāng)無線傳感網(wǎng)絡(luò)規(guī)模較大，實(shí)現(xiàn)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信需要消耗很多能量，為此，考慮將無線傳感器節(jié)點(diǎn)進(jìn)行分簇。分簇拓?fù)浣Y(jié)構(gòu)具有較好的可擴(kuò)展性，適合大規(guī)模網(wǎng)絡(luò)，與平面拓?fù)浣Y(jié)構(gòu)相比，更容易克服傳感器節(jié)點(diǎn)移動帶來的問題。

LEACH 算法進(jìn)行周期性工作，每輪的循環(huán)過程為：在簇的建立階段，每個節(jié)點(diǎn)選取一個介于0 到1 的隨機(jī)數(shù)，如果這個隨機(jī)數(shù)小于LEACH 算法所計算的閾值，該節(jié)點(diǎn)成為簇頭，簇頭向所有節(jié)點(diǎn)廣播自己成為簇頭的消息，每個節(jié)點(diǎn)根據(jù)接收到的廣播信號的強(qiáng)弱來決定加入哪個簇，并回復(fù)該簇頭[5-6]。利用LEACH 算法生成的網(wǎng)絡(luò)拓?fù)?，與平面拓?fù)浣Y(jié)構(gòu)相比，可以延長網(wǎng)絡(luò)生命周期，但也存在一定的缺陷，首先網(wǎng)絡(luò)簇頭完全隨機(jī)選取，沒有考慮節(jié)點(diǎn)的剩余能量，能量較少的節(jié)點(diǎn)當(dāng)選簇頭，會加快節(jié)點(diǎn)的死亡，其次，網(wǎng)絡(luò)節(jié)點(diǎn)的位置也是完全隨機(jī)的，分布不均勻，造成嚴(yán)重的數(shù)據(jù)冗余和鏈路沖突阻塞。

LEACH 算法中，p 是簇頭所占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率；r 是目前循環(huán)進(jìn)行的輪數(shù)，G 是最近1/p 輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合，當(dāng)節(jié)點(diǎn)n 在集合G 中時，由LEACH 算法的計算的T(n)可通過p 與(1-px[rmod(1/p)])的比值得到，當(dāng)n 不在集合G 中時，T(n)＝0，從T(n)我們可以看出，當(dāng)選簇頭的節(jié)點(diǎn)在接下來的1/p 輪循環(huán)中將不能成為簇頭，剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)越大，節(jié)點(diǎn)生成小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大。

針對LEACH 算法的不足，DCHS(deterministic cluster-head election)將能量因素考慮進(jìn)來，改進(jìn)了T(n)的計算方法[7]。

rs 表示節(jié)點(diǎn)連續(xù)未當(dāng)選過簇頭的輪次。一旦當(dāng)選了簇頭，rs 重置為0。上述公式的改進(jìn)有效地解決了DCHS 的缺陷，綜合考慮了節(jié)點(diǎn)的能量和閾值大小對簇頭選取的影響，使算法更公平合理。

除了節(jié)點(diǎn)剩余能量，還要考慮到能量均衡，在簇頭選擇過程中，應(yīng)同時考慮簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離及節(jié)點(diǎn)度，在利用DCHS 選舉簇頭基礎(chǔ)上，利用下式確定簇的大小：

其中dmax、dmin 分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離的最大值和最小值，d(si，DS)表示節(jié)點(diǎn)si 到匯聚節(jié)點(diǎn)的距離。

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

為驗(yàn)證提出算法的可行性及正確性，仿真實(shí)驗(yàn)是在Matlab7.0 中進(jìn)行。圖1 所示為本文所提算法與LEACH、DCHS 算法的比較，三種算法的平均耗能差別不大，但所提算法要優(yōu)于兩種基礎(chǔ)算法。

圖1 MPBC、LEACH、DCHS 平均能量消耗比較

4 小結(jié)與展望

近年來，對無線傳感器網(wǎng)絡(luò)的研究已經(jīng)取得了卓有成效的研究，提出了許多改進(jìn)算法和新的協(xié)議，但目前的算法研究對象多為節(jié)點(diǎn)分布均勻的靜態(tài)網(wǎng)絡(luò)，而現(xiàn)實(shí)存在的網(wǎng)絡(luò)節(jié)點(diǎn)都是隨機(jī)部署的，很難保證節(jié)點(diǎn)分布均勻，且很多實(shí)際應(yīng)用中可能需要利用移動節(jié)點(diǎn)的配合完成任務(wù)，現(xiàn)有的靜態(tài)網(wǎng)絡(luò)算法不能滿足實(shí)際應(yīng)用的要求，所以應(yīng)該將視野轉(zhuǎn)到對動態(tài)網(wǎng)絡(luò)的研究，提出更為有效的、節(jié)省能量的適用于節(jié)點(diǎn)位置動態(tài)變化的拓?fù)?、路由協(xié)議。

［1］Huafeng Wu，Qiannan Zhang，Su Nie，Wei Sun，and Xinping Guan.An Energy Distribution and Optimization Algorithm in Wireless Sensor Networks for Maritime Search and Rescue[J].International Journal of Distributed Sensor Networks，vol.2013，Article ID 725869，8 pages，2013.doi：10.1155/2013/725869.

［2］Wang J W，Sun W Y.Improved HEED Based Trust Routing Algorithm for WSNs[J].Advanced Materials Research.2014，989：4405-4408.

［3］Sun B，Gui C，Jia Y，et al.Mobility entropy-based clusterhead selection algorithm for Ad Hoc Networks[J].Energy Procedia，2011，13：8617-8625.

［4］趙金晶，朱培棟，等.Ad hoc 網(wǎng)絡(luò)移動模型及其應(yīng)用[J].計算機(jī)工程與科學(xué)，2005，27(5)：15-16.

［5］孫天一，陳滌，等.無線傳感器網(wǎng)絡(luò)LEACH 協(xié)議的探討及改進(jìn)[J].信號與系統(tǒng)，2005，2(1)：32-33.

［6］Tao Liu，F(xiàn)eng Li.Power-efficient clustering routing protocol based on applications in wireless sensor networks[C]//Wireless Communications，Networking and Mobile Computing，Wicom 09.5th international Conference，2009：1-6.

［7］HandyMJ，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.