武莎莎， 王宏志*， 胡黃水, 王出航

(1.長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012;2.長春師范大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 吉林 長春 130032)

0 引 言

近年來，在國內(nèi)外研究學(xué)者的眼中無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)[1]研究炙手可熱，主要應(yīng)用于醫(yī)療檢測、環(huán)境監(jiān)測、軍事防御等不同領(lǐng)域，WSN可以在一個小型設(shè)備中實現(xiàn)傳感、計算和通信功能，但WSNs在功率、存儲以及計算過程方面受到限制[2]。主要是因為組合成WSN傳感器節(jié)點的能量有限，而且無法進(jìn)行充電[3]。WSN的核心技術(shù)是網(wǎng)絡(luò)層的路由協(xié)議，如何通過有效的路由算法減少網(wǎng)絡(luò)通信能耗和延長網(wǎng)絡(luò)的生命周期已經(jīng)成為當(dāng)今科研人員研究的熱門話題。

平面路由協(xié)議和分層路由協(xié)議是兩種路由算法[4]， LEACH協(xié)議作為經(jīng)典的分簇路由協(xié)議[5]具有諸多優(yōu)點,其核心思想是將網(wǎng)絡(luò)劃分為若干大小不同的簇，每一個簇中有一個簇頭(CH)節(jié)點,每個簇中的普通節(jié)點把信息數(shù)據(jù)匯聚到CH節(jié)點，每個CH節(jié)點通過單跳將數(shù)據(jù)發(fā)送到基站(BS)。雖然各節(jié)點輪流擔(dān)當(dāng)CH節(jié)點，使得網(wǎng)絡(luò)中能量消耗盡量均衡，但CH節(jié)點以單跳的方式將數(shù)據(jù)發(fā)送到接收器，而且簇頭節(jié)點的選擇具有隨機(jī)性，導(dǎo)致BS附近的CH節(jié)點過早死亡。隨后又有一些LEACH算法的改進(jìn)算法被提出，如LEACH-C[6]，它是一種集中式協(xié)議，其主要思想是把節(jié)點的剩余能量作為選擇CH節(jié)點的因素考慮進(jìn)來，集中控制CH節(jié)點的選舉,但是節(jié)點在每輪數(shù)據(jù)傳輸開始時需要將其剩余能量和位置數(shù)據(jù)發(fā)送到BS，這導(dǎo)致離BS較遠(yuǎn)的節(jié)點產(chǎn)生額外能量消耗。文獻(xiàn)[7]提出了一種混合式節(jié)能聚類算法HEED，其主要目的是通過多對一的通信模式實現(xiàn)最小化WSN的能量消耗和控制開銷來延長整個網(wǎng)絡(luò)壽命。但是在多跳協(xié)議的情況下，更靠近BS的節(jié)點通常需要承受更多的通信負(fù)載。Chao Sha等[8]提出了一種基于環(huán)空的能量平衡數(shù)據(jù)采集方法(AEBDC)，此算法提出了在候選簇頭的幫助下實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，不僅減少了CH節(jié)點的負(fù)荷，同時也減少了數(shù)據(jù)上傳期間緩沖溢出的可能性。但是在數(shù)據(jù)傳輸過程中，越靠近網(wǎng)絡(luò)內(nèi)環(huán)，需要越多的候選簇頭來轉(zhuǎn)發(fā)數(shù)據(jù)，增加了候選簇頭節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)所消耗的能量。CAMP路由協(xié)議是一種用于無線傳感器的簇群輔助多路徑路由協(xié)議[9]，該算法是將網(wǎng)絡(luò)區(qū)域中的非簇頭節(jié)點劃分兩類，兩類不同的非簇頭節(jié)點按照不同的工作約束條件將其數(shù)據(jù)轉(zhuǎn)發(fā)到下一跳節(jié)點，該算法實現(xiàn)了節(jié)點能耗的均勻消耗，但是CAMP協(xié)議將網(wǎng)絡(luò)區(qū)域劃分為相等的區(qū)域，忽略了數(shù)據(jù)傳輸期間的能量熱點問題，而且把非簇節(jié)點分為兩類，增加了網(wǎng)絡(luò)的復(fù)雜度。EEMRP算法[10]中提出了一種基于通信管理(CM)節(jié)點的管理方法，用于重建簇群和中繼多跳數(shù)據(jù)傳輸，CM節(jié)點共享了CH節(jié)點的工作量，減少了CH節(jié)點的能量開銷，但是網(wǎng)絡(luò)需要提前確定每個網(wǎng)格的劃分，這限制了算法的可擴(kuò)展性。為了提高網(wǎng)絡(luò)的擴(kuò)展性，Jianhua huang等[11]提出了一種環(huán)形扇形網(wǎng)格輔助路由協(xié)議(ASGRP)，主要通過使用層間最小能量消耗路由算法建立從CH節(jié)點到BS的路由，這種方法有效地平衡了節(jié)點的能量消耗，但是在劃分簇時，每個簇群的大小一樣，導(dǎo)致離BS較近的網(wǎng)格中CH節(jié)點的能量消耗過快。

文中提出了一種環(huán)形無線傳感器網(wǎng)絡(luò)能量平衡多跳路由算法(Energy balanced multi-hop routing algorithm for ring wireless sensor network， EMRA),主要是在LEACH算法的基礎(chǔ)上，采用環(huán)形無線傳感器網(wǎng)絡(luò)，同時在每個簇中引入CM節(jié)點，緩解了單個CH節(jié)點的能量負(fù)荷。在網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中，考慮了CH節(jié)點到BS所消耗的能量與CH節(jié)點到下一環(huán)中距離CH節(jié)點最近的CM節(jié)點所消耗的能量關(guān)系，來估算CH節(jié)點將數(shù)據(jù)發(fā)送到BS所需的跳數(shù)。同時也考慮了CH節(jié)點到CM節(jié)點的最短距離與CH節(jié)點到BS的距離關(guān)系，這使網(wǎng)絡(luò)的生命周期得到延長，也減少了網(wǎng)絡(luò)的能量消耗。

1 EMRA路由模型

1.1 EMRA網(wǎng)絡(luò)模型

假設(shè)檢測區(qū)域是半徑為R的圓形網(wǎng)絡(luò)區(qū)域，區(qū)域中有n個傳感器節(jié)點。該網(wǎng)絡(luò)具有如下特征：

1)整個圓形網(wǎng)絡(luò)被均分為b個圓環(huán)區(qū)域，BS位于整個圓形網(wǎng)絡(luò)的中心處，網(wǎng)絡(luò)部署后,BS把自己的坐標(biāo)信息發(fā)送給網(wǎng)絡(luò)中所有傳感器及節(jié)點；

2)每個傳感器節(jié)點的初始能量相同，并且每個節(jié)點的傳輸范圍和傳輸速率也相同；

3)網(wǎng)絡(luò)中的鏈路沒有沖突和重傳，網(wǎng)絡(luò)具有很好的連接性。

1.2 EMRA能耗模型

采用文獻(xiàn)[6]中的能量消耗模型，在距離為d的節(jié)點Ni和節(jié)點Nj之間發(fā)送和接收 1 bit數(shù)據(jù)所消耗的能量可以采用下式計算：

(1)

Er=Eelec,

(2)

(3)

式中:Eelec----一個傳感器節(jié)點發(fā)送或者接收1 bit數(shù)據(jù)所消耗的能量;

εfs----自由空間放大模型參數(shù);

εmp----多跳衰減放大模型參數(shù);

d(Ni,Nj)----節(jié)點Ni和節(jié)點Nj之間的距離。

文中采用自由空間放大模型，所以

d(Ni,Nj)

式中：d0----通信距離閾值。

CH節(jié)點融合的m個分別攜帶k1,k2,…,kmbit的信息所消耗的能量

(4)

2 EMRA算法設(shè)計

2.1 基本思想

EMRA算法主要是假設(shè)網(wǎng)絡(luò)中每一環(huán)的CH節(jié)點數(shù)目按照算術(shù)級數(shù)來分布，根據(jù)式(4)計算出每一個環(huán)的CH節(jié)點數(shù)，以及每一環(huán)中CH節(jié)點和CM節(jié)點的選舉概率，然后根據(jù)每一環(huán)中節(jié)點的剩余能量和節(jié)點到BS的距離選舉出CM節(jié)點和CH節(jié)點，最后比較CH節(jié)點到BS的通信能耗與CH節(jié)點到下一環(huán)中CM節(jié)點的通信能耗，來確定CH節(jié)點把數(shù)據(jù)傳輸?shù)紹S所需的跳數(shù)。其流程如圖1所示。

圖1 EMRA算法流程

2.2 CM節(jié)點和CH節(jié)點選舉過程

為了平衡網(wǎng)絡(luò)能量消耗，圓形網(wǎng)絡(luò)被均分為b個環(huán)形區(qū)域，每個環(huán)域的寬度為R/b,假設(shè)網(wǎng)絡(luò)中每一環(huán)中的簇頭節(jié)點數(shù)Ca(a=1,2,…,b),按照算術(shù)級數(shù)分布，其表達(dá)式為

Ca=2a-1,

(5)

(6)

式中:a----網(wǎng)絡(luò)的環(huán)數(shù);

Ca----每一環(huán)中的CH節(jié)點數(shù);

Nua----每一環(huán)節(jié)點數(shù);

p----CH節(jié)點選舉概率。

CM節(jié)點不僅承擔(dān)著數(shù)據(jù)的轉(zhuǎn)發(fā)重任，同時也對節(jié)點之間的通信起著重要作用，CM節(jié)點對自身的位置以及能量有著更嚴(yán)格的要求,所以EMRA算法先選擇CM節(jié)點，然后在余下的節(jié)點中再按照CH節(jié)點的選舉權(quán)值選擇CH節(jié)點。CM節(jié)點的選舉考慮到節(jié)點的剩余能量以及節(jié)點到BS的最短距離。

(7)

β=mindNiB,

(8)

式中：α----當(dāng)前輪次中節(jié)點的剩余能量與節(jié)點初始能量比值的最大值;

β----當(dāng)前輪次中節(jié)點到BS的最短距離。

CM節(jié)點的選舉閾值

(9)

式中：E0----節(jié)點的初始能量;

dNiB----節(jié)點Ni到BS的距離;

Ec----當(dāng)前節(jié)點的剩余能量;

r----當(dāng)前網(wǎng)絡(luò)CH節(jié)點的輪換次數(shù);

S----每輪結(jié)束后網(wǎng)絡(luò)中非簇頭節(jié)點集。

網(wǎng)絡(luò)的生命周期與CH節(jié)點的選舉密切相關(guān)，網(wǎng)絡(luò)中CH節(jié)點不僅需要融合簇內(nèi)節(jié)點所發(fā)送的信息，同時也需要把融合后的信息發(fā)送到BS，所以CH節(jié)點的通信能耗比較大。LEACH算法中CH節(jié)點的選擇具有隨機(jī)性，而且CH節(jié)點的選舉只考慮了CH節(jié)點的數(shù)目與網(wǎng)絡(luò)節(jié)點總數(shù)的關(guān)系。EMRA算法中對CH節(jié)點的選擇做了改進(jìn)，不僅考慮了節(jié)點的剩余能量，同時也考慮了節(jié)點到CM節(jié)點的距離與CM節(jié)點到BS距離的關(guān)系。

(10)

式中：γ----Nj到CM節(jié)點距離與CM節(jié)點到BS距離的比值,γ越大，把數(shù)據(jù)傳輸?shù)紹S所需能量就越少。

CH節(jié)點的選舉閾值

(11)

2.3 EMRA算法路由

無線傳感器網(wǎng)絡(luò)中節(jié)點的主要能量用來發(fā)送數(shù)據(jù)，在保證節(jié)點數(shù)據(jù)完整地傳輸?shù)紹S情況下，如何減少節(jié)點的能量消耗，延長網(wǎng)絡(luò)的生命周期，已經(jīng)成為當(dāng)今研究的熱門。EMRA算法中數(shù)據(jù)傳輸過程如圖2所示。

路由主要流程如下：

1)在數(shù)據(jù)傳輸階段開始時，網(wǎng)絡(luò)a環(huán)中某一簇內(nèi)的節(jié)點i把數(shù)據(jù)發(fā)送到CH節(jié)點Nic(xic,yic),i=1,2,3,…,n后，由CH節(jié)點Nic(xic,yic)進(jìn)行融合。

2)a環(huán)中的CH節(jié)點把所攜帶有自己的坐標(biāo)Nic(xic,yic)位置的信息mic在整個網(wǎng)絡(luò)中廣播。

3)當(dāng)網(wǎng)絡(luò)中a-1 環(huán)中的CM節(jié)點Nim(xim,yim)接收到網(wǎng)絡(luò)中節(jié)點Nic發(fā)送的廣播信息后，a-1 環(huán)中的CM節(jié)點Nim(xim,yim)同時也把自己的坐標(biāo)信息mim發(fā)送給a環(huán)中的CH節(jié)點。

4)a環(huán)中的CH節(jié)點根據(jù)a-1 環(huán)中CM節(jié)點所發(fā)來的信息，把數(shù)據(jù)傳輸?shù)絘-1環(huán)中距離自身位置最近的CM節(jié)點， CM節(jié)點負(fù)責(zé)轉(zhuǎn)發(fā)CH節(jié)點所傳輸?shù)臄?shù)據(jù)信息，然后數(shù)據(jù)再轉(zhuǎn)發(fā)下一跳中距離自己最近的CM節(jié)點，最終數(shù)據(jù)信息發(fā)送到BS，No(x0,y0)。

LEACH算法中CH節(jié)點直接把數(shù)據(jù)傳輸?shù)紹S，導(dǎo)致距離BS較遠(yuǎn)的CH節(jié)點因為較大的通信能耗而過早死亡。EMRA算法采用多跳的方式將數(shù)據(jù)傳輸?shù)紹S，通過比較CH節(jié)點把數(shù)據(jù)傳輸?shù)紹S所消耗的能量E1與CH節(jié)點把數(shù)據(jù)傳輸?shù)较乱画h(huán)中CM節(jié)點所消耗的能量E2，估算CH節(jié)點把數(shù)據(jù)傳輸?shù)紹S所需的跳數(shù)H。我們僅考慮CH節(jié)點把數(shù)據(jù)傳輸?shù)紺M節(jié)點和BS這個過程所消耗的能量。

(12)

(13)

(14)

(15)

(16)

式中:dHB----CH節(jié)點到BS的距離;

dHM----CH節(jié)點到下一跳CM節(jié)點的距離;

nc----CH節(jié)點Nic內(nèi)的簇成員節(jié)點;

l----數(shù)據(jù)包的長度。

3 性能仿真分析

文中提出的算法是在MATLAB2014a中進(jìn)行的仿真實驗，主要是在WSN區(qū)域為100×100的仿真環(huán)境中進(jìn)行了多次實驗，同時與LEACH算法進(jìn)行比較，主要從網(wǎng)絡(luò)中的節(jié)點死亡率、網(wǎng)絡(luò)總能耗、網(wǎng)絡(luò)平均節(jié)點剩余能量三個方面分析了EMRA算法的性能。仿真實驗環(huán)境參數(shù)設(shè)置見表1。

表1 仿真環(huán)境參數(shù)設(shè)置

LEACH算法和EMRA算法在不同節(jié)點死亡率的情況下，網(wǎng)絡(luò)中CH節(jié)點的輪換次數(shù)變化如圖3所示。

從圖中可以看出，EMRA算法在CH節(jié)點輪換次數(shù)為942輪時網(wǎng)絡(luò)中第一個節(jié)點開始死亡，而LEACH算法在385輪時已經(jīng)有節(jié)點死亡。而且在網(wǎng)絡(luò)中節(jié)點的死亡率為50%時，EMRA算法的CH節(jié)點的輪換次數(shù)已經(jīng)達(dá)到1 325輪，而LEACH算法的CH節(jié)點輪換次數(shù)為779輪。這說明EMRA算法可以減少網(wǎng)絡(luò)中節(jié)點的能量消耗，緩解CH節(jié)點的負(fù)荷。

網(wǎng)絡(luò)能量消耗隨著CH節(jié)點輪換次數(shù)的變化如圖4所示。

從圖中可見，隨著網(wǎng)絡(luò)中每一輪CH節(jié)點輪換次數(shù)的增加，無論是EMRA算法，還是LEACH算法，它們的網(wǎng)絡(luò)能耗都在增加。在CH節(jié)點輪換次數(shù)為1 000輪時，EMRA算法中網(wǎng)絡(luò)能耗曲線變得平緩。LEACH算法的網(wǎng)絡(luò)能量消耗已經(jīng)達(dá)到4.453 1 J,此時EMRA算法的網(wǎng)絡(luò)能耗是3.388 4 J。這說明EMRA算法中采用多跳的路由算法可以減少網(wǎng)絡(luò)的能量消耗，延長網(wǎng)絡(luò)生命周期。

網(wǎng)絡(luò)中平均節(jié)點剩余能量隨著CH節(jié)點輪換次數(shù)增加的變化如圖5所示。

從圖中可見，在網(wǎng)絡(luò)初始階段時， EMRA算法和LEACH算法網(wǎng)絡(luò)中節(jié)點平均剩余能量曲線不斷減少，直到網(wǎng)絡(luò)中開始出現(xiàn)節(jié)點死亡，網(wǎng)絡(luò)中的平均節(jié)點剩余能量才突然變得緩慢且具有波動性，主要是因為網(wǎng)絡(luò)中存活節(jié)點數(shù)開始不斷減少，對網(wǎng)絡(luò)中的剩余能量沒有產(chǎn)生很大影響。EMRA算法中平均節(jié)點剩余能量曲線始終在LEACH算法上面，這進(jìn)一步說明EMRA算法在減少網(wǎng)絡(luò)節(jié)點能耗、平衡網(wǎng)絡(luò)能耗以及延長網(wǎng)絡(luò)生命周期上具有更優(yōu)越的性能。

4 結(jié) 語

提出一種環(huán)形無線傳感器網(wǎng)絡(luò)能量平衡多跳路由算法EMRA，主要是在LEACH算法的基礎(chǔ)上進(jìn)行改進(jìn)。首先在環(huán)形網(wǎng)絡(luò)中的每一環(huán)中引入CM節(jié)點，然后又提出了對CH節(jié)點和CM節(jié)點選舉的約束條件，最后在數(shù)據(jù)傳輸過程中考慮了CH節(jié)點到BS的跳數(shù)。仿真實驗結(jié)果表明，EMRA算法在減少CH節(jié)點能耗、平衡網(wǎng)絡(luò)能量以及延長網(wǎng)絡(luò)生命周期上有明顯的優(yōu)勢。