基于分簇的無線傳感器網絡數據收集協議研究

王 靚，范德輝

（1.復旦大學 信息科學與工程學院，上海 200433；2.青島職業技術學院，山東 青島 266555）

基于分簇的無線傳感器網絡數據收集協議研究

王 靚1，2，范德輝2

（1.復旦大學 信息科學與工程學院，上海 200433；2.青島職業技術學院，山東 青島 266555）

為延長無線傳感器網絡（WSN）的壽命，在傳統的典型分簇算法LEACH和EADEEG的基礎上進行改進，提出了一種新的基于分簇結構的數據收集協議—IDCP（Improued Data Collectiou Protocot，IDCP），在簇首形成階段和數據轉發傳遞階段分別提出了新的簇首形成算法和簇內數據轉發算法.在簇首形成階段，引入對節點可靠度指標的考量；在數據轉發傳遞階段，所有簇內普通節點對需要轉發的信息首先進行判斷分析，再決定是否進行信息傳遞.仿真實驗結果表明：與傳統協議相比較，改進算法在簇首選擇和數據轉發上都具有更好的網絡處理能力和更高的效率，有效延長了網絡生存周期.

無線傳感器網絡；分簇；數據收集；能量

無線傳感器網絡（WSN）是一種靈活度高、能量有限的網絡，在軍事國防、生物醫療、環境監測、交通管理和家庭等各個領域擁有十分廣闊的應用前景，對人類發展具有十分重要的影響［1－2］.多數情況下，傳感器網絡中節點的供電電源能量有限，因此，如何有效利用網絡能量、提高效率是WSN協議設計所面臨的首要問題［3］.

從網絡拓撲結構角度來看，WSN協議可以分為平面路由［4］協議和分簇路由協議［5］，平面路由協議中的節點沒有層次差異［6］，級別相同；分簇路由協議將具有某種關聯的網絡節點劃分為簇，每個簇內有一個簇首和多個簇內成員，根據等級的不同簇被劃分為多層結構，基站與最高層簇首通信，最高層簇的簇內成員是低一級簇的簇首，層層關聯，將整個網絡劃分為相連的多個區域.

在WSN分簇算法研究中，最早的分簇路由協議有LEACH（Low Energy AdaptiveClustering Hierarchy），該算法是目前比較成熟且常用的分簇路由算法［3］.LEACH算法采用隨機簇首選擇機制，具有實現簡單、操作靈活和可擴展性好等優點，但容易形成網絡內節點能量損耗不均衡的狀態，個別節點過早死亡，網絡的整體性能差.在國內，劉明等人［2］提出了一種基于能量感知的無線傳感器網絡數據收集協議—EADEEG（Energy－Aware Distributed Energy－Efficient data Gathering protocol for wireless sensor networks，EADEEG）.EADEEG算法由簇內各節點平均剩余能量的多少作為是否成為簇首的判斷條件，使各節點耗能比較平均，較好地解決了網絡內節點能量損耗不均衡問題.但在實際網絡中，由于節點所處環境和自身設計等原因，能量并不能作為參選簇首的唯一標準，還需綜合考慮節點感知數據的精確度.

本研究在前面2種協議的研究基礎上，著重對EADEEG協議的簇首選取過程以及簇內通信過程進行研究、改進和仿真，提出了一種改進的基于分簇結構的數據收集協議—IDCP.一方面，在簇首形成階段，充分考慮了簇節點的感知可靠度和 網絡性能等因素，有效提高了節點加入簇的效率，從而延長網絡壽命；另一方面，在簇拓撲形成后的數據轉發傳遞階段，對簇內普通節點要轉發給簇首的數據進行“判斷分析”式的轉發處理，將相鄰2個Δt時間內的信息做期望值分析，如果大于一個判斷期望值，表明周圍信息變化較大，則進行信息傳遞，否則表明周圍信息變化不明顯，將不再轉發該信息到簇首節點，從而達到了減少網絡無用通信、延長網絡壽命的效果.同時，本研究利用Matlab仿真實驗環境，對2種經典算法協議和改進的IDCP算法協議進行了模擬仿真，分別把3種算法在簇首形成算法和簇內數據轉發算法兩方面的節點死亡時間進行了對比.

1 基于分簇的數據收集協議

1.1 簇首形成算法

1.1.1 算法描述

LEACH算法定義了“輪”的概念，一輪由初始化和穩定工作2個階段組成.初始化即簇準備階段，該階段根據相應算法選出簇首，形成自適應簇的簇拓撲結構；穩定工作階段即就緒階段，完成整個監測區域數據的轉發和聚集［3，7］.WSN中每個節點的身份都用全網唯一的數值進行標識，這個數值定義為該節點的ID.同時，為了記錄相鄰節點發送來的信息，每個節點都需要儲存一張鄰居表.

在簇首形成算法中，節點ri在每輪（簇拓撲結構形成和數據轉發、聚集的一個周期）開始時，都以規定的半徑r為范圍向所有鄰居節點發送參加選舉的信息，信息內容包括該節點的ID、剩余能量Er和節點的可靠度指標Dp，每個節點按照所有鄰居節點發來的選舉消息更新自身鄰居表［2］，每輪更新一次.

然后，求出每個節點所有鄰居節點的平均剩余能量

式（1）中，rj（1≤j≤m，j≠i）代表節點ri半徑內的鄰居節點，Er表示該節點的剩余能量，m表示所有鄰居節點的數量.

每個節點申明成為簇首的時間（從每輪開始到本節點申明成為簇首消息的時刻對應的時間長度）定義為：

式（2）中，k是位于［0.9，1］區間的隨機均勻分布的實數值；T是假設確定的簇首選擇算法的持續時間；Dp為節點的可靠度指標，即節點的感知效率.

在每一輪中，如果一個節點在“申明成為簇首”的時間t前沒有收到所有鄰居節點發出的“申明成為簇首”的消息，那么該節點將向鄰居節點廣播“申明成為簇首”消息，從而成為該區域的簇首.如果該節點在其“申明成為簇首”的時間t前已經收到了鄰居節點廣播的“申明成為簇首”的消息，則該節點將放棄成為簇首的競爭，由發出廣播“申明成為簇首”消息的鄰居節點成為該區域的簇首.由此可見，每個節點申明成為簇首的時間越短，也就能越早地成為簇首，

由式（2）可知，只要滿足下面2個條件，1個節點將有更高的幾率成為簇首：

（2）可靠度指標Dp值越大，即節點的感知效率越高.

1.1.2 算法實現

簇首結構的生成算法如下所示：

1.2 簇內數據轉發算法

1.2.1 算法描述

為判斷信息量發生變化的情況，在每個Δtj里，節點持續計算其方差值DX，并與較小的δ值進行比較，若DX≥δ，則將新的信息轉發給簇首節點用作數據更新；若DX＜δ，說明信息變化不大，則不將該信息向簇首節點轉發，簇首節點默認選用前一時間信息進行聚集.簇內轉發算法的實現有效減少了不必要的網絡通信，提高了有效信息的傳送效率，減低了網路損耗，延長了網絡壽命.

1.2.2 算法實現

簇內數據轉發算法對要轉發的數據進行篩選，然后將信息發給簇中的簇頭作聚合，以減少不必要的通信量，節省資源.具體算法流程為：

2 仿真實驗

2.1 實驗方法

分別對LEACH協議、EADEEG協議和IDCP協議進行仿真實驗，從簇首結構形成算法和簇內轉發算法兩方面對3種算法對網絡壽命和網絡性能的影響進行比較，主要對3種不同算法下節點的死亡時間進行比較.實驗中，隨著各輪數據收集的進行，節點死亡時間出現越晚，網絡壽命越長；同時，網絡中各節點死亡時間相差越短，節點能量均衡性就越好，網絡整體性能也就越好.

仿真實驗在Matlab環境下進行，實驗場景設定的監測區域面積為100m×100m，在該區域內部署100個節點，且隨機分布，每個節點的初始能量服從（0，1）上的均勻分布，匯集點的位置為（50，200），默認數據分組的長度為500字節，控制消息長度為25字節.

2.2 實驗結果

2.2.1 IDCP簇首形成算法對網絡性能的影響

圖1是簇首形成算法在3種協議下全部節點死亡時間的比較.由圖1可以看出，LEACH協議第1個節點的死亡時間和最后1個節點的死亡時間相差達到200輪，各節點能量消耗嚴重不平衡，個別節點過早消耗掉，只有剩余節點工作，導致網絡整體的性能變差.同時，圖1中IDCP協議和EADEEG協議全部節點的死亡時間都非常接近，說明在真實環境中，每個節點在上述2種協議情況下，都能夠平均承擔網路整體的能量消耗，整個網絡的壽命也得到延長.IDCP協議和EADEEG協議的性能非常接近，這主要是因為IDCP協議和EADEEG協議的目標都是期望達到均勻的簇內分布.但IDCP協議以t作為簇首競爭的參數，與EADEEG協議相比能夠更快、更精準地選擇到合適的簇首，并減少了由于簇首選舉時間等待而造成的能量消耗.

圖1 簇首形成算法節點死亡時間的比較Figure 1 Timing of nodes'death（algorithm of cluster head selection）

2.2.2 IDCP簇內轉發算法對網絡性能的影響

圖2是簇內轉發算法節點死亡時間的比較.由圖2可以看出，IDCP協議、LEACH協議和EADEEG協議對應的3種算法的第1個節點死亡時間非常接近，但隨著時間的增加，IDCP協議中等量節點的死亡時間比LEACH協議要推遲近100～200輪，而比EADEEG協議要推遲幾十甚至一百輪，時間越久效果越明顯.這主要是因為IDCP協議簇內轉發算法將節點感知到的數據進行了篩選，只將更新的數據進行轉發，冗余數據則不轉發.因此，節點轉發的數據量相對減少，有效降低了網路損耗，延長了整個網絡的壽命.

圖2 簇內轉發算法節點死亡時間的比較Figure 2 Timing of nodes'death（forwarding algorithm of cluster）

3 結論

對傳統的分簇算法進行改進，提出了IDCP協議，在簇首競爭上，引入改進機制，在實現成本不增加的前提下，能夠保證簇首在網絡中的均勻分布；同時有效提高了節點加入簇的效率，在簇內數據轉發上，引入篩選機制，轉發有用數據，屏蔽冗余數據，減少無謂的通信損耗，從而提高了網絡的工作效率，延長了網絡的生命周期.

［1］ Akyildiz I F，Su W，Sankarasubramanian Y.Wireless sensor networks：A survey［J］.Computer Networks Joumal，2002，38（4）：393－422.

［2］ 劉明，曹建農，陳貴海，等.EADEEG：能量感知的無線傳感器網絡數據收集協議［J］.軟件學報，2007，18（5）：1092－1109.

［3］ 林楠，史葦杭.無線傳感器LEACH算法的優化及仿真［J］.計算機仿真，2011，28（1）：178－181.

［4］ Liu Z H，Ma J F.Asymmetric key pie—distribution scheme for sensor networks ［J］.IEEE Transactions on Wireless，2009，3：1366－1372.

［5］ 劉慶，王培康.無線傳感器網絡的安全分簇路由協議［J］.計算機仿真，2009，26（4）：167－171.

［6］ 孫奎杰.無線傳感器網絡分簇路由協議研究［D］.吉林：吉林大學，2007：4－10.

［7］ 卿利，朱清新，王明文.異構傳感器網絡的分布式能量有效成簇算法［J］.軟件學報，2006，17（3）：481－489.

Research on data collection protocol based on clustering for wireless sensor network

WANGLiang1，2，FANDehui2
（1.School of Information Science and Engineering，Fudan University，Shanghai 200433，China；
2.Qingdao Technical College，Qingdao 266555，Shandong Province，China）

In order to extend the lifetime of WSN，based on the studying of the traditional typical clustering algorithms of LEACH and EADEEG，a novel data collection protocol named IDCP is proposed by making improvement，and new clustering topology formation algorithm and new data forwarding algorithm are proposed during clustering formation and data forwarding stage.In setting stage，the introduction of the reliability index of the node is proposed.In data forwarding stage，all forwarded information is analyzed by all common nodes in clusters and the information is analyzed according to the expected value.If the analysis result is less than the expected value，information will not be transmitted，otherwise information will be transmitted.Experiments and results analysis show that，the improved algorithm considers the effects on node energy and sense reliability factor properly，it is better than the traditional algorithms in cluster head selection and data forwarding and its network processing ability and performance are both better.

wireless sensor network；clustering；data collection；energy

TP393

A

1671－1114（2011）03－0063－04

2010－10－04

王 靚（1979—），女，講師，主要從事RFID無限傳感器網絡方面的研究.

（責任編校 紀翠榮）