WSN中的基于能量和鄰居數(shù)的分層路由協(xié)議

韓冰 彭太樂 肖建于

摘要：為了完成數(shù)據(jù)的采集和傳輸?shù)耐瑫r(shí)最小化能耗，無線傳感器網(wǎng)絡(luò)需要節(jié)能且健壯的通訊協(xié)議，國(guó)內(nèi)外學(xué)者提出了一些基于能量的簇頭選擇算法。然而這些所提算法里面均未考慮簇頭鄰居的能量和數(shù)目。該文提出了一個(gè)基于能量的簇頭選擇算法EBC，該算法中簇頭是基于節(jié)點(diǎn)和節(jié)點(diǎn)鄰居的能量和節(jié)點(diǎn)的鄰居數(shù)目來選擇的。實(shí)驗(yàn)表明EBC相比LEACH 提高了無線傳感器網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：EBC;LEACH協(xié)議;無線傳感器網(wǎng)絡(luò);多跳通信;HEED

中圖分類號(hào)：TP393? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）22-0045-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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 引言

無線傳感器網(wǎng)絡(luò)是由一組傳感器節(jié)點(diǎn)構(gòu)成的無線網(wǎng)絡(luò)，其目的是感知并采集網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，并將感知信息發(fā)送給監(jiān)測(cè)者。在無線傳感器網(wǎng)絡(luò)的研究中，能效一直是熱點(diǎn)問題。為了延長(zhǎng)網(wǎng)絡(luò)生存周期，國(guó)內(nèi)外學(xué)者得到了大量的研究。

分簇算法可以有效延長(zhǎng)網(wǎng)絡(luò)生存周期，在分簇算法中，簇頭的選擇對(duì)網(wǎng)絡(luò)能耗有較大影響[1]。本文對(duì)分簇算法的簇頭選擇進(jìn)行研究，提出了一種新的簇頭選擇算法。

2 相關(guān)工作

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

3 EBC分簇算法

EBC分簇算法包括以下步驟： 數(shù)據(jù)收集，基于能量和基于節(jié)點(diǎn)度的簇頭選擇。下面分別介紹這兩個(gè)步驟：

3.1 數(shù)據(jù)收集

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

3.2 EBC簇頭選擇過程

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

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

為了減少簇內(nèi)通信的能耗，簇頭應(yīng)盡可能分布于節(jié)點(diǎn)密集的區(qū)域。在本文假設(shè)的網(wǎng)絡(luò)中，每個(gè)簇的最佳覆蓋面積 S =[L2p×N]，最佳簇半徑 R = [L2p×N][9]。本文將到節(jié)點(diǎn) i的距離小于 R的節(jié)點(diǎn)稱為 i的鄰節(jié)點(diǎn)，[ni] 為 i的鄰節(jié)點(diǎn)數(shù)，根據(jù)式（2）設(shè)置競(jìng)爭(zhēng)因子 η，即

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

為了使[ni]? 大的節(jié)點(diǎn)優(yōu)先成為簇頭，設(shè)置延時(shí)時(shí)間

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

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

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

基站接收建簇信息，當(dāng)收到 P ×N個(gè)建簇信息后廣播簇頭選舉結(jié)束信息。未成為簇頭的節(jié)點(diǎn)收到該信息后，根據(jù)收到的信號(hào)強(qiáng)度，加入最近的簇頭，向其發(fā)送入簇信息并附上自身 ID。簇頭接收入簇信息，向發(fā)出請(qǐng)求的節(jié)點(diǎn)返回一確認(rèn)信息，完成簇的建立。節(jié)點(diǎn)采集信息，通過時(shí)分多址（TDMA）方式送給簇頭并附上自身剩余能量信息。簇頭進(jìn)行數(shù)據(jù)融合后發(fā)給基站。基站接收采集的信息數(shù)據(jù)并收集和各個(gè)節(jié)點(diǎn)的剩余能量信息。一輪結(jié)束后返回步驟一循環(huán)執(zhí)行。

4 仿真結(jié)果分析

模擬器使用的是NS2，NS2是一款用來分析網(wǎng)絡(luò)性能的離散事件驅(qū)動(dòng)的模擬器。在這個(gè)仿真中，有一個(gè)仿真區(qū)域1，420 × 500節(jié)點(diǎn)分布在其中，和AODV路由協(xié)議。EBC仿真用到的參數(shù)如表1所示。

4.1包遞交速率

包遞交比例（PDR）是一個(gè)測(cè)試網(wǎng)絡(luò)性能的服務(wù)質(zhì)量參數(shù)，低 PDR降低網(wǎng)絡(luò)的性能。

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

4.2 包丟失率

包丟失率是一個(gè)節(jié)點(diǎn)可能丟棄的最大數(shù)據(jù)包數(shù)目，如圖2所示，EBC 分簇算法的包丟失率比LEACH要小。

4.3 剩余能量

一個(gè)節(jié)點(diǎn)的剩余能量是一個(gè)節(jié)點(diǎn)所剩的能量。圖3表明 EBC的剩余能量比LEACH高許多。

5? 總結(jié)

EBC 是一種簇頭選擇算法，該算法通過節(jié)點(diǎn)和節(jié)點(diǎn)鄰居的能量和節(jié)點(diǎn)鄰居的數(shù)目來選擇簇頭節(jié)點(diǎn)， 仿真表明 EBC scheme相比其他只考慮簇頭能量的簇頭選擇算法提高了網(wǎng)絡(luò)的生命周期，進(jìn)一步的工作可以是簡(jiǎn)化一下EBC的過程。

參考文獻(xiàn)：

[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.

【通聯(lián)編輯：代影】