基于作用力模型的傳感器網絡簇型協議*

何杏宇，楊桂松，周亦敏

(1.上海理工大學 實驗室管理與服務中心，上海200093;2.上海理工大學 光電信息與計算機工程學院，上海200093)

0 引 言

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

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

1 網絡模型

本文定義的網絡模型為:1)網絡中的節點結構和初始能量相同，且能量不可補給，在部署后具有可移動性和獲知其位置信息的能力;2)采用文獻［9］中的無線通信能量計算模型。

2 基于作用力模型的移動簇型協議

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

2.1 簇的建立階段

2.1.1 簇頭選舉

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

其中，Eresidual為節點的剩余能量，Eaverage為節點的鄰居節點的平均剩余能量，如果節點的剩余能量大于鄰居節點的平均能量則成為簇頭節點的概率增大，反之，減小;1/p 為網絡節點中簇頭比例為p 時每個簇包含的節點數量，Nneigbor為鄰居節點數量，N 為網絡的節點總數量，當鄰居節點數量比1/p 多時，該區域簇頭節點數量增加，反之，減少。

2.1.2 簇頭節點的自適應移動

在簇頭選舉后和簇頭節點進行自適應移動之前，應先獲取簇頭節點移向的位置。為此，本文提出一個與距離和剩余能量相關的作用力模型，該模型設簇頭節點最終移向的位置為目標點，假定q 個簇成員節點將在與簇頭節點連線方向上分別產生q 個牽引力，牽引力大小與其剩余能量和其與簇頭之間的距離相關，第i 個簇成員產生的牽引力fi的計算公式為

其中，α，β 為權重系數，Li為第i 個簇成員節點與簇頭節點之間的距離，Ei為第i 個簇成員的剩余能量。這q 個簇成員對簇頭分別產生q 個牽引力，距離簇頭越遠的節點產生的牽引力越大，反之，越小;剩余能量越小的節點產生的牽引力越大，反之，越小。該模型由勢能最小原理(一個力學系統處于平衡狀態時勢能最小)要求這q 個簇成員在目標點位置所產生的多個牽引力的合力為0。

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

圖1 簇成員和目標點的位置關系Fig 1 Location relationship between cluster members and target point

首先，將簇頭節點和三個簇成員節點的坐標轉換至以目標點為原點的(X'，Y')坐標系中。轉換后的目標點坐標為(X'0，Y'0)，(X'0，Y'0)=((X0－X0)，(Y0－Y0))=(0，0)，而三個簇成員節點的坐標的計算公式分別為

然后，根據三個簇成員和目標點的位置關系和剩余能量可以獲得以目標點為原點的作用力模型如圖2 所示:三個簇成員產生的牽引力矢量坐標分別為

圖2 作用力模型Fig 2 Force model

由式(4)可推導出

由于在目標點位置三個簇成員節點產生的三個牽引力f1，f2，f3對應的矢量和為0，亦即，X″1+X″2+X″3=0，Y″1+Y″2+Y″3=0，則可以推算出

根據式(5)，進而可以推算出

當q=3 時，目標點的計算公式為

對上述模型進行推廣，當簇頭節點接收到q 個簇成員的節點的坐標信息分別為(Xi，Yi)，i=1 ～q 時，則此時目標點的坐標計算公式為

2.2 主干路徑建立階段

在簇頭自適應移動后，為了在簇頭節點之間建立全連通的主干路徑，本文提出如圖3 所示的基于通信半徑和剩余能量的中繼節點選舉算法。當存在“孤立簇頭”時，便可按照圖3 所示算法進行中繼節點選舉。

圖3 中繼節點選舉算法流程圖Fig 3 Flow chart of relay node election algorithm

設定V 為判斷簇成員成為中繼節點的可能性大小的參數，V 的計算公式為

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

3 仿真與實驗

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

3.1 實驗參數設置

本文的仿真場景為400 個節點隨機部署在一個200 m×200 m 的正方形區域內，其Sink 節點位于正方形的中心。仿真參數如表1 所示。

表1 仿真參數Tab 1 Simulation parameters

3.2 實驗結果分析

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

圖4 節點能量消耗方差Fig 4 Energy consumption variance of nodes

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

4 結 論

圖5 節點存活的個數Fig 5 Number of alive nodes

本文提出的基于作用力模型的移動簇型協議在進行簇頭選舉時提高了剩余能量大的節點成為簇頭的概率，同時增加了節點密度較大區域簇頭節點的個數，該算法允許簇頭節點基于簇成員剩余能量和距離的牽引力作用下進行自適應移動，均衡了簇頭和簇成員之間的通信代價。同時，本文提出的中繼節點選舉算法，實現了簇頭節點之間的全連通。實驗結果證明:本文提出的協議能夠有效地均衡網絡能耗，顯著地延長網絡的生命周期。

［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，Fahmy 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］ 龔本燦，蔣廷耀，汪祥莉.一種基于剩余能量的無線傳感器網絡分簇協議［J］.計算機工程與應用，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］ 喬俊峰，劉三陽，曹祥宇.無線傳感器網絡中基于節點密度的簇算法［J］.計算機科學，2009，36(12):46－49.

［6］ 路成杰，蔣海峰.一種基于節點密度的無線傳感器網絡協議［J］.傳感器與微系統，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.