WSN中的基于能量和鄰居數的分層路由協議

韓冰 彭太樂 肖建于

摘要：為了完成數據的采集和傳輸的同時最小化能耗，無線傳感器網絡需要節能且健壯的通訊協議，國內外學者提出了一些基于能量的簇頭選擇算法。然而這些所提算法里面均未考慮簇頭鄰居的能量和數目。該文提出了一個基于能量的簇頭選擇算法EBC，該算法中簇頭是基于節點和節點鄰居的能量和節點的鄰居數目來選擇的。實驗表明EBC相比LEACH 提高了無線傳感器網絡的生命周期。

關鍵詞：EBC;LEACH協議;無線傳感器網絡;多跳通信;HEED

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）22-0045-03

開放科學（資源服務）標識碼（OSID）：

A Hierarchical Routing Protocol based on Energy and Number of Neighbors for WSN

HAN Bing1，PENG Tai-le 2，XIAO jian-yu2

（1. College of? Management， Huaibei Normal University， Huaibei 235000，China; 2. College of? Computer Science，Huaibei Normal University， Huaibei 235000，China）

Abstract： Wireless sensor network requires robust and energy efficient communication protocols to minimize the energy consumption as much as possible. Numerous energy-based cluster head election algorithms have been proposed and implemented. However， the capacities and workloads of the neighbors of cluster heads have not been considered in large wireless sensor networks. A energy-based cluster （EBC） head selection scheme where cluster heads are elected based on the energy value of a node and the energy values of its neighbors and the number of its neighbors is proposed in this paper. Simulations in network simulator have proved that EBC cluster head selection scheme has improved the lifetime of the network compared to the LEACH protocol.

Key words： EBC;LEACH protocol; Wireless sensor network; Multi-hopcommunication; HEED

1 引言

無線傳感器網絡是由一組傳感器節點構成的無線網絡，其目的是感知并采集網絡覆蓋區域中感知對象的信息，并將感知信息發送給監測者。在無線傳感器網絡的研究中，能效一直是熱點問題。為了延長網絡生存周期，國內外學者得到了大量的研究。

分簇算法可以有效延長網絡生存周期，在分簇算法中，簇頭的選擇對網絡能耗有較大影響[1]。本文對分簇算法的簇頭選擇進行研究，提出了一種新的簇頭選擇算法。

2 相關工作

國內外學者在這個領域進行了大量的研究，一些比較優秀的可以有效延長網絡生存周期的分簇算法出現。LEACH算法是最早出現的無線傳感器網絡分簇算法，在LEACH中，每一個簇頭節點直接和基站通訊，這樣當簇頭節點和基站距離較遠時它們之間的通訊會消耗簇頭節點大量的能量。針對LEACH算法的缺點， Xiangning [2]提出了多跳LEACH（multi-hop LEACH）該協議通過其他簇頭節點選擇簇頭和基站的最佳路徑，通過這些簇頭節點傳輸數據。簇頭之間是通過多跳通信傳輸數據的，根據所選的最佳路徑，這些簇頭把數據傳到一個距離基站最近的簇頭。Younis and Fahmy [3]提出了HEED算法，HEED算法基于節點度和剩余能量從一組節點選擇簇頭節點，實驗表明HEED相比LEACH進一步延長了無線傳感器網絡的生命周期。本文提出的算法EBC（energy-based cluster）選舉簇頭時充分考慮了節點的剩余能量，獲得較好的性能。

3 EBC分簇算法

EBC分簇算法包括以下步驟： 數據收集，基于能量和基于節點度的簇頭選擇。下面分別介紹這兩個步驟：

3.1 數據收集

在這個階段，基站從所有節點獲得節點的能量數據，然后我們獲得每一個節點的鄰居列表，我們考慮鄰居列表中每一個節點的能量值以做出有效的簇頭選擇決定。所有這些節點都必須在簇頭候選節點的一跳范圍之內，我們考慮節點的能量和鄰居數以決定把簇頭候選節點變成簇頭，還是再選一個簇頭候選節點。

3.2 EBC簇頭選擇過程

簇頭是比普通節點擁有更多能量的節點。簇頭選擇的過程分簇算法的一個核心過程，由于無線傳感器網絡資源有限，簇頭選擇不能太復雜，但還必須選出合適的簇頭。簇頭選擇過程的第一步是發現具有最大能量的節點。數據收集過程完成后，我們獲得了所有節點的能量，然后我們分析節點的能量已找到具有最大能量的節點。然后我們計算一個參數活躍能量值，該值是一個為了計算一個成為簇頭的節點的能量和鄰居節點能量的關系而設計的參數。該值是通過AvgE（j）和e（n）計算的。

Ce（n）=W1* AvgE（j）+W2*e（n）? ? ? ? ? ? ? ? ? ? ? ? （1）

為了減少簇內通信的能耗，簇頭應盡可能分布于節點密集的區域。在本文假設的網絡中，每個簇的最佳覆蓋面積 S =[L2p×N]，最佳簇半徑 R = [L2p×N][9]。本文將到節點 i的距離小于 R的節點稱為 i的鄰節點，[ni] 為 i的鄰節點數，根據式（2）設置競爭因子 η，即

[ηi] =1 -min[[ni]? ×p，1]? ? ? ? ? ? ? （2）

為了使[ni]? 大的節點優先成為簇頭，設置延時時間

[ti]=（[ηi] +γ）×[t0]? ? ? ? ? ? ? ? ? ?（3）

式中[t0]為選定的時間;γ為隨機數且 γ∈[0，1]。對于節點 i，若其可以成為簇頭，則在簇頭選取時首先延時[ti]。[ti]到時若簇頭選取仍未結束，則 i成為簇頭。節點的Ce（n）值找出來以后，如果該值大于一個閾值thresh，則該節點開始延遲。延時結束時該節點成為簇頭，廣播建簇信息，信息中包含自身的 ID。其他節點接收建簇信息，估算距離，按式（4）更自身延時時間。一般來說，簇頭均勻分布可以減少能耗[9]，本文通過調整[ti] 來促使簇頭均勻分布。若一個節點成為簇頭，則以事先選定的強度發送建簇信息。其他節點接收該信息，根據接收信號的強度估算到該簇頭的距離l。并按式（4）更新延時時間。

[ti=ti+t0 l≤Rti? ?l>R]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

基站接收建簇信息，當收到 P ×N個建簇信息后廣播簇頭選舉結束信息。未成為簇頭的節點收到該信息后，根據收到的信號強度，加入最近的簇頭，向其發送入簇信息并附上自身 ID。簇頭接收入簇信息，向發出請求的節點返回一確認信息，完成簇的建立。節點采集信息，通過時分多址（TDMA）方式送給簇頭并附上自身剩余能量信息。簇頭進行數據融合后發給基站。基站接收采集的信息數據并收集和各個節點的剩余能量信息。一輪結束后返回步驟一循環執行。

4 仿真結果分析

模擬器使用的是NS2，NS2是一款用來分析網絡性能的離散事件驅動的模擬器。在這個仿真中，有一個仿真區域1，420 × 500節點分布在其中，和AODV路由協議。EBC仿真用到的參數如表1所示。

4.1包遞交速率

包遞交比例（PDR）是一個測試網絡性能的服務質量參數，低 PDR降低網絡的性能。

圖1表明隨著仿真時間的增加，EBC算法比LEACH算法顯著增加了PDR。

4.2 包丟失率

包丟失率是一個節點可能丟棄的最大數據包數目，如圖2所示，EBC 分簇算法的包丟失率比LEACH要小。

4.3 剩余能量

一個節點的剩余能量是一個節點所剩的能量。圖3表明 EBC的剩余能量比LEACH高許多。

5? 總結

EBC 是一種簇頭選擇算法，該算法通過節點和節點鄰居的能量和節點鄰居的數目來選擇簇頭節點， 仿真表明 EBC scheme相比其他只考慮簇頭能量的簇頭選擇算法提高了網絡的生命周期，進一步的工作可以是簡化一下EBC的過程。

參考文獻：

[1] A.K. Thomas， R. Devanathan.Variable duty-cycle based efficient network discovery in WSN.Eur. J. Sci. Res. 2012， 93（2）： 266–278.

[2] F. Xiangning， S. Yulin.Improvement on LEACH protocol of wireless sensor network， inInternational Conference on Sensor Technologies and Applications （SensorComm '07）， IEEE，October 2007：260–264.

[3] O. Younis， S. Fahmy.HEED： a hybrid， energy-efficient， distributed clustering approach for adhoc sensor networks. IEEE Trans. Mob. Comput.2004， 3（4）：366–379 .

[4] A. Abbasi， M. Younis.A survey on clustering algorithms for wireless sensor networks.Comput. Commun， 2007，2826–2841.

[5] R. Tandon， B. Dey， S. Nandi.Weight based clustering in wireless sensor networks， in Proceedings of the IEEE National Conference on Communications （NCC），2013.

[6] S.H.N. Choi， K.O. Lee， K.W. Rim.A weight-based unequal clustering routing protocol in wireless sensor network， in Proceedings of IEEE International Conference on Information and Communication Technology （ICT4M），2010.

[7] L.H.M. Mercy， K. Balamurugan， M. Vijayaraj.Maximization of lifetime and reducing power consumption in wireless sensor network using protocol. Int. J. Soft Comput. Eng. （IJSCE） ，2013， 29（6）.

[8] D.G. Reina， S.L. Toral， P. Jonhson， F. Barrero.Hybrid flooding scheme for mobile ad hoc networks. IEEE Commun. Lett，2013： 17（3）.

[9] Su J S Guo W Z Yu C L， et al. Fault-tolerance clustering in algorithm with load-balance aware in wireless sensor networks[J]. Chinese Journal of Computers，2014 ，37（2）：445-456.

【通聯編輯：代影】