基于移動預測的海上無線傳感網絡分簇算法

周 倩 張 琳

（上海海事大學，中國 上海 201306）

1 系統模型

1.1 基于移動模型的節點動態預測

海上無線傳感器網絡，節點呈現高度的動態性。為此，采用移動模型對節點狀態進行模擬，移動模型是對網絡中移動節點移動方式的抽象，反應了移動節點的位置、速度、加速度的變化情況。在現有的研究中，移動模型又有不同的分類方式，根據移動模型的構建方式不同，移動模型分成蹤跡移動模型(Trace Mobility Model，TMM)與合成移動模型(Synthetic Mobility Model，SMM)兩類[4]。針對海上環境的特點，假設分布在海上的無線傳感器節點的運動趨勢是基本一致的，將組移動模型應用到無線傳感器網絡拓撲中，充分考慮節點間的位置關系，適當刪除冗余鏈路，構建合理拓撲。

在這個模型中，節點運動呈現一致性，具有一個相同的基礎速率和基礎移動方向，為了表示各節點移動狀態的差異性，各個節點的移動速率是由組移動速率加上隨機附加速率。

根據節點的運動狀態對節點未來的移動狀態進行預測，假設t 時刻得到節點的移動速率為v（t），移動方位為Φ（t），預測得到的t 時刻節點的移動速率為v1（t），移動方位為Φ1（t），預測t+1 時刻節點的移動速率為v2(t)，移動方位為Φ2（t），它們之間存在如下遞推關系：v2（t）＝(1-α)v1（t）+αv（t），v2（t）＝(1-β）Φ1（t）+βΦ（t）。

根據上述遞推公式，可以在t 時刻根據得到的移動目標的運動速率和方位以及歷史的預測結果預測出節點在t+1 時刻的運動速率。

2 改進的分簇協議

本文采用[1]中所提到的無線電傳播模型，根據無線信號傳播能量損耗模型可知，當無線傳感網絡規模較大，實現從源節點到目的節點的通信需要消耗很多能量，為此，考慮將無線傳感器節點進行分簇。分簇拓撲結構具有較好的可擴展性，適合大規模網絡，與平面拓撲結構相比，更容易克服傳感器節點移動帶來的問題。

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

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

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

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

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

其中dmax、dmin 分別表示網絡中的節點到匯聚節點的距離的最大值和最小值，d(si，DS)表示節點si 到匯聚節點的距離。

3 實驗仿真

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

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

4 小結與展望

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

［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 網絡移動模型及其應用[J].計算機工程與科學，2005，27(5)：15-16.

［5］孫天一，陳滌，等.無線傳感器網絡LEACH 協議的探討及改進[J].信號與系統，2005，2(1)：32-33.

［6］Tao Liu，Feng 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.