一種基于地理位置的無線傳感器網(wǎng)絡(luò)路由算法

肖 達,肖明波

(1.諾基亞通信系統(tǒng)技術(shù)(北京)有限公司杭州研發(fā)中心, 浙江 杭州 310052; 2.杭州電子科技大學(xué)通信工程學(xué)院, 浙江 杭州 310018)

一種基于地理位置的無線傳感器網(wǎng)絡(luò)路由算法

肖 達1,肖明波2

(1.諾基亞通信系統(tǒng)技術(shù)(北京)有限公司杭州研發(fā)中心, 浙江 杭州 310052; 2.杭州電子科技大學(xué)通信工程學(xué)院, 浙江 杭州 310018)

針對基于地理位置信息的不同節(jié)點密度算法 (GLIDND)在能量有效性上的不足，為無線傳感器網(wǎng)絡(luò)提出了一種改進的基于地理位置信息的不同節(jié)點密度算法Enhanced-GLIDND.該算法從如下幾個方面對GLIDND算法進行了改進:(1)根據(jù)能耗比在不同區(qū)域撒布不同密度的備用節(jié)點；(2)簇頭的更替采用消息通知機制；(3)簇間蟻群路由算法將下一跳節(jié)點所在簇的累計能耗作為影響因子.仿真試驗將Enhanced-GLIDND與EEF，GLIDND，LEACH和BCDCP算法作比較.結(jié)果表明，Enhanced-GLIDND算法在網(wǎng)絡(luò)生命周期和能量有效性上都明顯優(yōu)于其他各算法.

無線傳感器網(wǎng)絡(luò)；不同節(jié)點密度；簇；網(wǎng)絡(luò)生命周期

無線傳感器網(wǎng)絡(luò)被認為是21世紀(jì)最重要的技術(shù)之一，它將對人類未來的生活方式產(chǎn)生巨大影響.麻省理工學(xué)院的《技術(shù)評論》雜志(Technology Review)[1]評出了對人類未來生活產(chǎn)生深遠影響的十大新興技術(shù),無線傳感器網(wǎng)絡(luò)位于這十種新技術(shù)之首.無線傳感器網(wǎng)絡(luò)是一種無基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)，它綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù),能夠協(xié)作地實時監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象的信息，并對這些數(shù)據(jù)進行處理，獲得詳盡而準(zhǔn)確的信息，將其傳送到需要這些信息的用戶.

在無線傳感器網(wǎng)絡(luò)中，一般由一個或多個節(jié)點充當(dāng)數(shù)據(jù)匯聚點(BS節(jié)點)網(wǎng)絡(luò)中傳感器節(jié)點收集的數(shù)據(jù)，通過多跳的方式傳送到BS節(jié)點，BS節(jié)點將融合后的數(shù)據(jù)通過有線或無線的方式傳送給觀察者.在通信方式上，無線電、紅外、聲波等多種無線通信技術(shù)的發(fā)展為微傳感器間通信提供了多種選擇，尤其是以IEEE802.15.4為代表的短距離無線電通信標(biāo)準(zhǔn)的出現(xiàn)，為無線傳感器網(wǎng)絡(luò)的發(fā)展奠定了堅實的基礎(chǔ).

作為當(dāng)今信息領(lǐng)域新的研究熱點，無線傳感器網(wǎng)絡(luò)涉及多學(xué)科交叉的研究領(lǐng)域，有很多相關(guān)的技術(shù)有待研究，例如：網(wǎng)絡(luò)拓撲控制、網(wǎng)絡(luò)協(xié)議、定位技術(shù)、數(shù)據(jù)融合.而網(wǎng)絡(luò)拓撲控制具有最重要的意義.通過拓撲控制，自動生成良好的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，能夠提高路由協(xié)議和MAC協(xié)議的效率，可為數(shù)據(jù)融合、時間同步和目標(biāo)定位等很多方面奠定基礎(chǔ)，有利于節(jié)省節(jié)點的能量，從而延長網(wǎng)絡(luò)生命周期.所以，拓撲控制是無線傳感器網(wǎng)絡(luò)研究的核心技術(shù)之一.

本論文主要從層次型網(wǎng)絡(luò)拓撲組織這個方面展開研究，對經(jīng)典層次型拓撲組織算法LEACH[2]，BCDCP[3]進行深入分析，并針對我們之前提出的GLIDND算法的不足之處，提出一種改進的GLIDND層次型網(wǎng)絡(luò)拓撲組織算法Enhanced-GLIDND.

1 GLIDND路由算法

無線傳感器網(wǎng)絡(luò)的節(jié)能路由算法往往都希望將能耗和負載均衡結(jié)合得盡可能完美.在層次型拓撲結(jié)構(gòu)組織這個方向上，最早出現(xiàn)的一個算法就是LEACH算法.LEACH定義了“輪”(Round)的概念，每一輪存在初始化階段和穩(wěn)定階段兩個狀態(tài).初始化階段是簇頭的形成階段.每個節(jié)點決定在當(dāng)前“輪”中是否成為簇頭，成為簇頭的概率是一個建議的固定值，需要根據(jù)網(wǎng)絡(luò)中節(jié)點的數(shù)目而定.在初始化階段，每一個節(jié)點在0到1中選取一個隨機數(shù)，如果這個隨機數(shù)小于這一“輪”所設(shè)定的門限值Thresh，那么這個節(jié)點就成為簇頭.在隨機產(chǎn)生出簇頭后，成為簇頭的節(jié)點再向網(wǎng)絡(luò)廣播分簇信息，告知其他節(jié)點產(chǎn)生了一個新的簇頭.其他節(jié)點接收到分簇消息后，根據(jù)信號強度來選擇它要加入的簇群，并通知相應(yīng)的簇頭.這樣在初始化階段，就構(gòu)成了以多個簇頭為核心的簇群.各簇群中的節(jié)點通過TDMA方式與簇頭進行通信.在穩(wěn)定階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，傳給簇頭.簇頭先對從各節(jié)點接收來的數(shù)據(jù)進行必要的數(shù)據(jù)融合處理，再將數(shù)據(jù)包轉(zhuǎn)發(fā)給BS節(jié)點.LEACH算法能夠相應(yīng)地延長網(wǎng)絡(luò)生命周期，但是該算法還存在很多不足的地方，如每次建立簇的過程會產(chǎn)生一定的額外開銷，能量有效性較低；簇頭選舉的隨機性使得簇頭在地理位置上的分布不均勻；以及在大規(guī)模網(wǎng)絡(luò)中，由于功率限制，節(jié)點并不一定能單跳向BS發(fā)送數(shù)據(jù)等.因此該算法還需要進一步完善和改進.目前，已經(jīng)有很多學(xué)者在LEACH算法基礎(chǔ)上提出了改進算法.

BCDCP算法針對LEACH算法的簇頭節(jié)點分布不均勻的特性，在建立簇的過程中，于大于平均能量的節(jié)點中，選出兩個相距最遠的節(jié)點，作為簇頭，將整個網(wǎng)絡(luò)分為兩個子簇，然后將子簇分割成更小的簇，直至分割到BS節(jié)點規(guī)定的簇頭數(shù)目為止[3].這種分簇算法雖然保證了簇頭節(jié)點在地理位置上分布的大致均勻，但是每輪的成簇開銷非常大.針對LEACH算法單跳和BS節(jié)點通信的弊端，在簇間路由的問題上，BCDCP協(xié)議用多跳路由機制將數(shù)據(jù)傳送給基站.路徑的選擇是先通過最小生成樹算法[4]將所有簇頭節(jié)點連通，然后隨機選擇一個簇頭節(jié)點作為最終將數(shù)據(jù)傳給基站的節(jié)點.隨機選擇簇頭傳遞數(shù)據(jù)給基站有一定的合理性，因為太頻繁地利用距離基站近的節(jié)點作為數(shù)據(jù)到達基站前的最后一跳，會嚴(yán)重消耗距離基站較近的節(jié)點的能量.因此，BCDCP算法的隨機選擇簇頭傳遞數(shù)據(jù)給BS節(jié)點，將能耗平均地分配給了所有簇頭節(jié)點.但是，這種簇間路由算法雖然將能耗在所有簇頭節(jié)點間平均化了，但是在能量的有效性上不敢恭維.如果最遠離BS節(jié)點的簇頭被選為所有簇頭節(jié)點匯聚數(shù)據(jù)到達BS節(jié)點前的最后一跳，那么能量的有效性還不如LEACH算法中簇頭節(jié)點單跳與BS節(jié)點通信.

針對這兩種典型的層次結(jié)構(gòu)路由協(xié)議存在的問題，我們曾經(jīng)提出一種更優(yōu)的層次結(jié)構(gòu)路由算法GLIDND[5].該算法借鑒GAF算法按虛擬單元格劃分簇的思想[6]，將監(jiān)測區(qū)域劃分成若干固定的邏輯區(qū)域，形成一個個虛擬的網(wǎng)格(簇).并提出了“層”(level)(圖1)的概念，把劃分完單元格的距離BS節(jié)點垂直距離相同的一行單元格定義為一“層”.每一個簇內(nèi)，根據(jù)剩余能量和地理位置信息選舉出簇頭，這就保證了簇頭分布的均勻性.只有在簇頭的能量低于某個閾值時，才需要更換簇頭.這就避免了每“輪”成簇時的大量廣播信息所消耗的能量.簇間路由采用一種改進的蟻群算法[7]，節(jié)點間距和節(jié)點剩余能量將作為兩個主要的影響因素.這就保證了在蟻群算法收斂到最優(yōu)路徑以后，不會過度地使用某條路徑而導(dǎo)致某些簇頭節(jié)點因能量快速耗盡而對整個網(wǎng)絡(luò)造成影響.達到了在同一“層”不同簇之間的負載平衡.但是，鄰近BS節(jié)點的簇頭，因為轉(zhuǎn)發(fā)了大量數(shù)據(jù)，消耗了過多能量，而成為“熱區(qū)”[8].距離BS越近，轉(zhuǎn)發(fā)數(shù)據(jù)消耗的能量越多，于是，GLIDND算法根據(jù)劃分邏輯區(qū)域后各區(qū)域能耗的大小，也可理解為距離BS節(jié)點的遠近來決定備用節(jié)點密度的方法來解決熱區(qū)問題.但是，GLIDND算法仍然存在若干缺點：

虛擬單元格分簇的思想保證了簇頭分布的大致均勻性，但是，在每一個簇內(nèi)，根據(jù)剩余能量和地理位置信息選舉簇頭的方案在中心位置簇頭節(jié)點能量消耗過多而被輪換時，不得不選舉出非中心位置的傳感器節(jié)點作為簇頭，降低了能量有效性.這種在單個簇內(nèi)輪換簇頭的方式是在以犧牲能量有效性換取負載均衡.

在每一個簇內(nèi)，只有在簇頭節(jié)點的能量低于某一閾值時，此簇才需要更通過選舉方式更換簇頭節(jié)點，一定程度上降低了LEACH，BCDCP算法每輪成簇時的廣播開銷.但是，通過選舉方式更換簇頭仍然需要大量的廣播開銷.

根據(jù)各區(qū)域距離BS節(jié)點的遠近，在不同“層”撒布不同密度的備用節(jié)點的方案在一定程度上解決了“熱區(qū)”問題.但是，在每一個區(qū)域，節(jié)點主要能耗實際上都集中在地理位置偏中心的簇頭節(jié)點，而不是整個簇.于是，在同一“層”的整個區(qū)域內(nèi)均勻地撒布備用節(jié)點是不夠明智的.

簇間路由采用以下一跳簇頭節(jié)點剩余能量和節(jié)點間距為影響因子的蟻群算法來均衡同一“層”不同簇之間的負載，容易出現(xiàn)偏差.比方說某簇頭節(jié)點有兩個鄰居簇頭節(jié)點可以作為下一跳，A節(jié)點的剩余能量為30%，B節(jié)點的剩余能量為80%，GLIDND算法很可能選取B節(jié)點作為下一跳.然而，B節(jié)點雖然剩余能量更多，它可能是因為本簇能量消耗過快而被重新選舉出的第N(N>1)個簇頭，A節(jié)點很可能是因為本簇能量消耗過慢還不曾被替換過的第一個簇頭.所以，下一跳簇頭節(jié)點剩余能量這一個影響因子并沒有真實反映各簇的真實負載.

針對GLIDND算法的以上不足，我們提出了一種改進的GLIDND算法Enhanced-GLIDND.改進的GLIDND算法可以歸納為以下四個部分.

在第一“輪”循環(huán)開始時，首先，將這個傳感區(qū)域進行劃分，這個行為只出現(xiàn)在第一“輪”，以后的循環(huán)過程不會再對傳感區(qū)域進行劃分.其次，將GLIDND算法中在不同區(qū)域撒布不同密度備用節(jié)點的思想細化.根據(jù)對不同“層”之間簇頭節(jié)點的能耗比預(yù)計，在不同“層”各簇的中心區(qū)域撒布不同密度的備用節(jié)點，同一“層”內(nèi)各簇的中心區(qū)域備用節(jié)點密度相同.每一個簇內(nèi)，根據(jù)簇頭節(jié)點和單個非簇頭節(jié)點的能耗比預(yù)計，在非中心區(qū)域給予非簇頭節(jié)點相應(yīng)數(shù)目的備用節(jié)點補給.Enhanced-GLIDND算法這種比GLIDND更加細化的撒布不同密度的備用節(jié)點的方案將能量有效性和縱向負載均衡結(jié)合得更好.

在第一“輪”循環(huán)進行區(qū)域劃分之后便開始確立簇頭，建立簇、簇頭多跳路徑.確立簇頭時，綜合考慮了節(jié)點剩余能量以及地理位置信息.建立簇頭多跳路徑的過程中，蟻群算法以鄰居節(jié)點所在簇的累計能耗和節(jié)點間距作為影響因子.Enhanced-GLIDND算法選取簇間路由的影響因子更真實反映了不同簇的能耗，有效地均衡了橫向負載.

第二“輪”后，每“輪”循環(huán)開始時，如果上一“輪”的簇頭節(jié)點在上“輪”結(jié)束時的能量低于閾值0.2E0，此節(jié)點將發(fā)送一個消息通知距離它最近的節(jié)點(備用節(jié)點或簇內(nèi)節(jié)點)作為新的簇頭.該新簇頭將其位置和能量等基本信息廣播，簇內(nèi)非簇頭節(jié)點收到此廣播報文后與新簇頭協(xié)調(diào)TDMA調(diào)度.鄰居簇頭節(jié)點收到此廣播報文后，據(jù)此更新簇間路由.選擇下一跳的過程同第一“輪”一致.否則，不需要重新確立簇頭.Enhanced-GLIDND算法由當(dāng)前簇頭節(jié)點消息通知距離最近的鄰居節(jié)點作為新簇頭的方案節(jié)省了GLIDND算法重新選舉簇頭所需要發(fā)送的大量廣播包.

在每“輪”循環(huán)中，當(dāng)簇頭、簇頭多跳路徑以及TDMA調(diào)度均確定下來之后，節(jié)點便可以進行數(shù)據(jù)傳輸了.簇內(nèi)的成員節(jié)點根據(jù)TDMA調(diào)度，在自己所在時隙內(nèi)向簇頭發(fā)送數(shù)據(jù)，簇頭按照多跳路徑的方向發(fā)送數(shù)據(jù)，直至將數(shù)據(jù)發(fā)送給BS節(jié)點.

2 改進的GLIDND算法

2.1傳感區(qū)域的劃分

改進的GLIDND算法Enhanced-GLIDND在區(qū)域劃分上與GLIDND算法完全一致.根據(jù)GLIDND算法的設(shè)計思想，在進行分簇之前需要將整個傳感區(qū)域進行劃分，從傳感器的計算能力和能量局限性考慮，Enhanced-GLIDND算法將劃分區(qū)域任務(wù)交給了BS節(jié)點，首先傳感區(qū)域內(nèi)的傳感器節(jié)點需要將自己的地理位置信息發(fā)送給BS節(jié)點，BS節(jié)點收集到這些信息之后進行統(tǒng)一劃分.最后，BS節(jié)點再將劃分之后的結(jié)果廣播給傳感區(qū)域內(nèi)的各個傳感器節(jié)點，給所有傳感器節(jié)點分配對應(yīng)的Cluster ID(簇ID).下面介紹具體的區(qū)域劃分過程.這里僅考慮一般的網(wǎng)絡(luò)情況，即BS在整個傳感區(qū)域之外，并且距離整個傳感區(qū)域比較遠的位置，如圖1所示.

圖1 Enhanced-GLIDND算法拓撲圖

這里我們先假設(shè)節(jié)點傳輸距離為R，為保證任意相鄰單元格可以互相通信，必須滿足：

R2>(2r)2+(2r)2

(1)

圖2 傳輸距離的設(shè)定

接下來我們將說明劃分出多少個區(qū)域數(shù)才能達到能量的最優(yōu)利用，以及如何在不同區(qū)域撒布不同密度的備用節(jié)點.

2.2最優(yōu)區(qū)域個數(shù)和不同區(qū)域備用節(jié)點密度的確定

將目標(biāo)區(qū)域劃分成一個個小的邏輯區(qū)域可以縮小數(shù)據(jù)通信距離，提高能效.同時各個區(qū)域并行運行成簇算法，也使網(wǎng)絡(luò)響應(yīng)速度得以提高.但是，區(qū)域數(shù)量的多少直接影響簇的數(shù)量和大小，根據(jù)目標(biāo)區(qū)域面積、節(jié)點數(shù)量等參數(shù)來優(yōu)化區(qū)域數(shù)量是提高系統(tǒng)整體性能的必然要求.

設(shè)有N個節(jié)點布置在面積為M*M的正方形目標(biāo)區(qū)域中，目標(biāo)區(qū)域被劃分為m2個邏輯小區(qū)域，平均每個區(qū)域節(jié)點數(shù)為N/m2個.主要的能量消耗包括：每個簇頭接收簇成員的數(shù)據(jù)，數(shù)據(jù)融合，發(fā)送數(shù)據(jù)給鄰居簇頭(Ech)；成員節(jié)點發(fā)送數(shù)據(jù)給簇頭(Enon-CH)；各簇頭的路由能耗(Ech-ch).

根據(jù)Enhanced-GLIDND算法中區(qū)域劃分的思想，最靠近BS的一組簇頭(level=m)，將收集到的本簇內(nèi)的數(shù)據(jù)融合后直接發(fā)送給BS.其他簇頭(level

Ech=

(2)

=

式中：

Eelec：發(fā)送電路和接收電路消耗的能量；

EDA：節(jié)點進行數(shù)據(jù)融合消耗的能量；

εfs：自由空間衰減信道模式放大指數(shù)；

εmp：多徑衰減信道模式放大指數(shù)；

dCH-CH:簇頭節(jié)點間距；

dtoBS: 簇頭節(jié)點到基站的距離；

M：區(qū)域邊長；

N：節(jié)點個數(shù)；

m：最優(yōu)“層”數(shù)；

各簇的主要能耗都集中在位于中心區(qū)域的簇頭，大部分備用節(jié)點的補給也集中在中心區(qū)域，于是，我們認為dCH-CH=r, 設(shè)dtoCH表示簇成員節(jié)點到簇頭的通信距離，則每個簇內(nèi)節(jié)點和本簇簇頭的通信能耗為

Enon-CH=βEelec+βεfsd2to-CH

(3)

E(d2to-CH)=?(x2+y2)ρ(x,y)dxdy

(4)

圖3 單個簇內(nèi)節(jié)點分布

因此，一個簇內(nèi)的能耗為

(5)

令Ecluster=

路由能耗表示為Ech-ch, 對于level=m的簇頭，將收到的包轉(zhuǎn)發(fā)給BS，對于level

(6)

各簇頭的路由能耗Ech-ch主要指簇頭接收鄰居簇頭的數(shù)據(jù)并轉(zhuǎn)發(fā)給路由方向的鄰居簇頭的能耗.鑒于所有簇頭的數(shù)據(jù)包的最后一跳都是由level=m的區(qū)域內(nèi)的簇頭轉(zhuǎn)發(fā)給BS，我們將每個簇頭產(chǎn)生的數(shù)據(jù)包被轉(zhuǎn)發(fā)的次數(shù)計為n+1(n=1,2…m-1)的形式.level=1的區(qū)域內(nèi)簇頭產(chǎn)生的數(shù)據(jù)包經(jīng)過(m-2)+1次轉(zhuǎn)發(fā)到達BS，level=2的區(qū)域內(nèi)簇頭產(chǎn)生的數(shù)據(jù)包經(jīng)過(m-3)+1次轉(zhuǎn)發(fā)到達BS，……，level=m-1的區(qū)域內(nèi)簇頭產(chǎn)生的數(shù)據(jù)包經(jīng)過0+1次轉(zhuǎn)發(fā)到達BS，level=m的區(qū)域內(nèi)簇頭產(chǎn)生的數(shù)據(jù)包不需要被轉(zhuǎn)發(fā)，因此，不需要消耗轉(zhuǎn)發(fā)能量.

因為每一“層”有m個簇，于是，在監(jiān)測區(qū)域(level

于是，系統(tǒng)總能耗

Etotal=m*Ecluster1+(m2-m)*Ecluster2+hop_e*Ech-ch1+hop_i*Ech-ch2

(7)

(8)

(9)

由(8)(9)兩式，我們可以得到使得總能耗最小的m解.下面，我們來看看如何撒布備用節(jié)點.這是Enhanced-GLIDND算法的最核心之處.

表1 一“輪”內(nèi)各節(jié)點的能耗

由表1可知，每一“輪”，非簇頭節(jié)點的主要能耗用于向簇頭節(jié)點發(fā)送一個βbit的報文，因此，不同“層”各簇內(nèi)非簇頭節(jié)點的總能耗基本是一致的.不同“層”的能耗差異主要體現(xiàn)在簇頭節(jié)點，簇頭節(jié)點的能耗決定了簇頭被替換的速率.因此，備用節(jié)點在不同“層”各簇中心區(qū)域的撒布密度應(yīng)當(dāng)以不同“層”之間簇頭的能耗比為依據(jù).撒布在不同“層”各簇中心區(qū)域的備用節(jié)點的密度比為：

ρlevel=m:ρlevel=m-1:…:ρlevel=1=Ech1+(m-1)Ech-ch1：Ech2+(m-2)Ech-ch2:…Ech2

(10)

當(dāng)然，我們也不能將所有備用節(jié)點都撒布在中心區(qū)域為簇頭節(jié)點作備份，如果當(dāng)中心區(qū)域仍然有若干備用節(jié)點未被激活，而非中心區(qū)域的非簇頭節(jié)點卻已經(jīng)開始死亡，我們是不能收集到整個檢測區(qū)域的完整而有效的信息的.于是，我們根據(jù)一“輪”內(nèi)單個非簇頭節(jié)點和簇頭節(jié)點的能耗比決定在每個非簇頭節(jié)點周圍撒布備用節(jié)點的密度.以第一“層”為例：

ρnon-CH:ρlevel=1=Enon-CH:Ech2

(11)

根據(jù)(11)式，我們不難知道如何在非中心區(qū)域的那些非簇頭節(jié)點周圍撒布備用節(jié)點.

2.3確立簇頭及簇頭多跳路徑階段

2.3.1 確立簇頭

由于第一“輪”和其他“輪”在確立簇頭的方式上有所差別，所以需要分開介紹.為方便說明，我們假設(shè)簇頭節(jié)點個數(shù)為k.Enhanced-GLIDND算法首輪確立簇頭的方式與GLIDND算法一致.

首輪：

步驟1:因為在首“輪”，所有節(jié)點能量都相等，都具有簇頭競選資格.于是，所有節(jié)點將自身基本信息(ID，Cluster ID，能量，坐標(biāo)，status)廣播出去，互通基本信息并宣布自己具有簇頭競爭資格，備用節(jié)點進入休眠狀態(tài).

步驟2: 依據(jù)簇內(nèi)能耗最小原則，BS根據(jù)每個網(wǎng)格(簇)內(nèi)具有競爭簇頭資格的非備用節(jié)點發(fā)出的信息分別計算出各競爭節(jié)點到簇內(nèi)其他節(jié)點的距離平方和S2.

步驟3：BS在每個網(wǎng)格(簇)內(nèi)選出S2最小的節(jié)點，將這些節(jié)點的k個節(jié)點的基本信息(ID ，Cluster ID，能量，坐標(biāo), status)在一個數(shù)據(jù)包里廣播出去.傳感器節(jié)點將接收到的廣播包中的ID逐一與自己比較，若有一個與自己的ID相同，則將status設(shè)置為cl_head，并根據(jù)其他k-1個簇頭的基本信息更新鄰居簇頭節(jié)點列表.無一相同則將status設(shè)置為cl_nonhead.

步驟 4：這一步是成簇最后的關(guān)鍵一步.本算法采用同LEACH算法一樣的TDMA機制，簇頭節(jié)點給每個簇內(nèi)節(jié)點分配一個時間片，節(jié)點會按照時間片的先后順序來發(fā)送數(shù)據(jù)給簇頭.

Enhanced-GLIDND算法在第二“輪”之后的簇頭確立方式是一個對GLIDND算法的主要改進點.

第二“輪”后：

步驟1: 對于任意一個簇，當(dāng)簇頭節(jié)點的剩余能量大于閾值0.2E0時，不需要更換簇頭.否則，發(fā)送一個消息通知距離其最近且剩余能量最多的鄰居節(jié)點(備用節(jié)點或簇內(nèi)節(jié)點)，這個節(jié)點成為新的簇頭，將status置為cl_head并將自身基本信息(ID，Cluster ID，能量，坐標(biāo)，status)廣播出去.

步驟2: 收到此廣播包的鄰居簇頭節(jié)點據(jù)此更新路由表.

步驟 3：簇頭節(jié)點給每個簇內(nèi)節(jié)點分配一個時間片，節(jié)點會按照時間片的先后順序來發(fā)送數(shù)據(jù)給簇頭.當(dāng)某個非簇頭節(jié)點的能量小于0.01E0時，它向最近的status為backup的節(jié)點發(fā)送一個激活消息，收到激活消息的備用節(jié)點將status置為cl_nonhead.并向鄰居節(jié)點廣播自身信息.

該方案確立簇頭的方式省去了GLIDND算法更換簇頭節(jié)點時，與BS通信產(chǎn)生的大量報文.本質(zhì)上也選取了地理位置最優(yōu)且剩余能量最多的節(jié)點作為簇頭，極大地提高了能量有效性.

2.3.2 簇頭多跳路徑階段

Enhanced-GLIDND算法中，簇頭多跳路徑也是對GLIDND算法簇頭路由的一個重要改進.在GLIDND算法中，剩余能量都初始化為E0，鏈路信息素濃度都初始化為τij(0)(τij(0)為常數(shù)).

下面的公式表示形成的或更新的簇頭與簇頭間的信息素濃度：

τij←(1-ρ)τij+a*energeα+lβ

(12)

式中ρ表示信息素的揮發(fā)程度，a，α表示節(jié)點剩余能量在信息素中所占的比重，l是簇頭間距，β表示節(jié)點間距離在信息素中所占的比重.從該公式我們可以發(fā)現(xiàn)，從整個數(shù)據(jù)傳輸過程來看，路徑的選擇不僅考慮歷史經(jīng)驗，算法提供的新的啟發(fā)信息也在發(fā)揮作用.和蟻群算法一樣，路徑上的信息素會隨著時間的推移有一定量的揮發(fā).所以上面的公式是由兩部分組成的.第一部分是實現(xiàn)一段時間內(nèi)的信息素的揮發(fā)，初始時信息素濃度為0，則揮發(fā)量也為0.第二部分是啟發(fā)信息，主要是根據(jù)與鄰居簇頭的距離以及鄰居簇頭的剩余能量來計算簇頭間的信息素濃度，信息素越大，被選擇作為下一跳的概率越大.因此，在選擇下一跳時，不僅要考慮是否是最短距離發(fā)送，還要折中考慮簇頭節(jié)點的能量.式中的參數(shù)，也和蟻群算法一樣，一般是通過實驗獲得，而無嚴(yán)格的數(shù)學(xué)理論支持.

然而，當(dāng)前簇頭節(jié)點的剩余能量并未反應(yīng)出此簇頭節(jié)點所在簇的真實負載，剩余能量多的簇頭節(jié)點所在簇的能耗速率很可能大于剩余能量少的簇頭節(jié)點所在簇的能耗速率.蟻群算法選路的目的是為了實現(xiàn)網(wǎng)絡(luò)的橫向負載均衡，因此，當(dāng)前簇頭節(jié)點的剩余能量并不適合作為蟻群算法的影響因子來實現(xiàn)橫向負載均衡.Enhanced-GLIDND算法以下一跳可選簇頭節(jié)點所在簇的累計能耗作為蟻群算法的影響因子，真實反映了各簇的負載.

(13)

式中a，α表示累計能耗在信息素中所占的比重，energe表示該簇頭節(jié)點所在簇的累計能耗,其他各變量含義與式(12)一致.

當(dāng)某個簇頭要發(fā)送數(shù)據(jù)時，根據(jù)路由表中相鄰簇頭的信息素濃度，計算出各個相鄰簇頭被選擇的概率.下面的公式表示簇頭到相鄰簇頭概率：

(14)

式中，N表示下一跳的可選區(qū)域.

3 仿真試驗

3.1仿真環(huán)境

LEACH算法是一種經(jīng)典的層次型無線傳感器網(wǎng)絡(luò)路由協(xié)議，目前許多層次型的路由協(xié)議都是在LEACH的基礎(chǔ)上提出的，例如BCDCP算法.本論文研究Enhanced-GLIDND算法的性能，我們采用與文獻[9]中LEACH算法相類似的仿真條件將Enhanced-GLIDND算法與GLIDND，LEACH,BCDCP，EEF(Energy Efficient Routing Algorithm)[10]算法進行了仿真和對比分析.

仿真條件：對于Enhanced-GLIDND算法，在100*100的正方形區(qū)域內(nèi)隨機均勻撒布100個節(jié)點，備用節(jié)點的數(shù)目若干，在這里我們?nèi)溆霉?jié)點總數(shù)為100.根據(jù)表2中的仿真參數(shù)和式(8),(9)確定最優(yōu)簇的個數(shù)為m = 2;于是，最優(yōu)簇個數(shù)為4.再根據(jù)仿真參數(shù)和式(10)(11):ρlevel=2:ρlevel=1:ρnon-CH=28.56∶22.4∶1,ρnon-CH取距離中心簇頭最遠的簇內(nèi)節(jié)點計算.我們發(fā)現(xiàn)，當(dāng)處于level=2的簇的中心簇頭節(jié)點已經(jīng)被消耗將近29個，level=1的簇的中心簇頭節(jié)點被消耗將近23個時，距離中心最遠的非簇頭節(jié)點才剛剛開始死亡，其他距離中心更近的節(jié)點當(dāng)然具備更多能量.于是，我們在level=2的簇中心位置撒布28個節(jié)點，level=1的簇中心位置撒布22個節(jié)點.BS節(jié)點，位于(50，175).每個無線傳感器節(jié)點的初始能量為0.5J，能量閾值為0.005J.對于LEACH，BCDCP及EEF算法，我們在正方形區(qū)域內(nèi)隨機均勻的撒布100個節(jié)點，100個備用節(jié)點.EEF算法隨機選舉10個節(jié)點作為簇頭節(jié)點.GLIDND算法按照論文[5]的方法在不同“層”均勻撒布不同密度的備用節(jié)點.仿真參數(shù)如表2所示：

表2 仿真參數(shù)設(shè)置

3.2結(jié)果分析

3.2.1 平均能量消耗

圖4 每“輪”(round)平均能量消耗比較

從圖4中我們可以看到，LEACH算法在1800“輪”左右耗盡網(wǎng)絡(luò)能量，BCDCP算法的平均能耗較LEACH有所減小，在2000“輪”左右才耗盡能量.GLIDND算法的平均能耗較BCDCP算法又有所減少，在2000“輪”左右時仍然有少許剩余.EEF算法在2000“輪”時，節(jié)點平均剩余能量大約為0.116J(23%).而Enhanced-GLIDND算法在平均能耗方面明顯優(yōu)于其他四種算法，在2000“輪”時節(jié)點平均能量剩余0.18J(36%).

這表明BCDCP算法較LEACH而言，簇頭以多跳向BS傳遞數(shù)據(jù)的方式減小了能耗，在一定程度上延長了網(wǎng)絡(luò)生命周期.GLIDND算法相對于LEACH和BCDCP而言，以固定成簇的方式避免了每“輪”成簇時大量廣播包的能量開銷.簇間路由方面，以BS為根節(jié)點構(gòu)造路由樹的方式，使得簇頭向BS傳遞數(shù)據(jù)的最后一跳總是在距離BS最近區(qū)域的簇頭，這種方式又比BCDCP算法更加節(jié)能.

EEF算法固定簇頭的方式，相對于LEACH，BCDCP而言，省去了每“輪”成簇的廣播包開銷，相對于GLIDND，省去了更換簇頭時選舉簇頭的開銷.根據(jù)可選下一跳簇頭的剩余能量、簇頭間距，可選前驅(qū)和后繼數(shù)目四個參數(shù)來決定簇間路由的方式，也遠比LEACH和BCDCP節(jié)能.

Enhanced-GLIDND算法以消息激活的機制更換新簇頭,省去了GLIDND算法需要更換簇頭時的廣播開銷. 簇間路由以各簇的累計能耗作為蟻群算法的影響因子,更加真實地反映了網(wǎng)絡(luò)的負載.改進的蟻群算法也更好地均衡了橫向負載，避免了GLIDND算法中蟻群算法因為選取下一跳簇頭節(jié)點剩余能量作為影響因子而對網(wǎng)絡(luò)橫向負載做出的誤判和因此產(chǎn)生的能量浪費.撒布的備用節(jié)點主要集中在中心區(qū)域,這種盡可能讓中心區(qū)域節(jié)點成為簇頭的方式,極大地減小了網(wǎng)絡(luò)平均能耗，也避免了EEF算法因為部分節(jié)點不在簇頭節(jié)點的無線傳輸范圍內(nèi)，借用接力節(jié)點傳輸數(shù)據(jù)而造成的能量損耗.

3.2.2 存活節(jié)點個數(shù)

從圖5中我們可以看到，LEACH在進行到第1200“輪”左右時，幾乎已無節(jié)點存活，而BCDCP算法依然有5個左右的節(jié)點，這就說明相對于LEACH，BCDCP算法在一定程度上延長了整個網(wǎng)絡(luò)生命周期.這主要是因為BCDCP算法在簇頭選舉階段就通過選舉節(jié)點能量足夠大的節(jié)點作為簇頭，從而使得低能量節(jié)點能夠延長它們的生命周期.此外，在簇間路由方面，根據(jù)MST(Minimum Spanning Tree)算法采用多跳的方式向BS發(fā)送數(shù)據(jù)，避免了單一簇頭節(jié)點因能耗過大而過早死亡.GLIDND算法在1200“輪”左右時，仍然有60個左右的節(jié)點.這是因為GLIDND算法采用基于地理位置固定劃分簇的方式減少了每“輪”成簇的開銷，在簇頭選舉的方式上繼承了BCDCP算法的簇內(nèi)能耗最小的思想，將節(jié)點剩余能量和地理位置信息都考慮在內(nèi).在簇間路由方面，以BS為根節(jié)點構(gòu)造由簇頭向BS發(fā)送數(shù)據(jù)的路由樹，減小了整個網(wǎng)絡(luò)的總能耗，對于由此而產(chǎn)生的“熱區(qū)”問題，提出了一種根據(jù)每一“輪”能耗的大小，在不同區(qū)域撒布不同數(shù)目備用節(jié)點的思想，極大地將能耗縱向平均化，延長了網(wǎng)絡(luò)生命周期.并且利用一種改進的蟻群算法，將簇頭節(jié)點的剩余能量加入信息素濃度的計算中，這樣，選擇下一跳節(jié)點時，通過一定概率選擇能量較大的節(jié)點，從而避免了單一節(jié)點因能量消耗過大而過早死亡.EEF算法在1200“輪”左右，有70個存活節(jié)點.在2000“輪”時仍然有40個節(jié)點.這說明EEF算法固定簇頭的方式較 GLIDND算法減少了更新簇頭時的廣播能耗，略微延長了節(jié)點壽命.

Enhanced-GLIDND算法在1200“輪”左右時,仍然有124個節(jié)點,在2000“輪”時仍然有50個節(jié)點,節(jié)點死亡速率也比較穩(wěn)定.這是因為相對于EEF，GLIDND算法,以消息通知的機制更換新簇頭, 將大部分備用節(jié)點撒布在各簇中心區(qū)域從而使簇頭長期保持在簇中心的方式,極大地節(jié)省了各節(jié)點能耗,延長了各節(jié)點的壽命.

圖5 每“輪”(round)存活節(jié)點個數(shù)比較

3.2.3 能量有效性

無線傳感器網(wǎng)絡(luò)的能量有效性是指該網(wǎng)絡(luò)在一定的能量條件下感知到的信息量.能量有效性是無線傳感器網(wǎng)絡(luò)的重要性能指標(biāo).到目前為止，無線傳感器網(wǎng)絡(luò)的能量有效性還沒有被模型化和量化，還不具有被普遍接受的標(biāo)準(zhǔn)，需要深入研究.一般是以單位能耗內(nèi)BS收到數(shù)據(jù)包的多少作為評價能量有效性的指標(biāo).定義：效率=BS收到數(shù)據(jù)包的個數(shù)/總能量消耗.我們的實驗中，對于不同算法，因為分簇數(shù)目以及簇間路由方式的不同，BS節(jié)點在一“輪”內(nèi)收到的數(shù)據(jù)包的個數(shù)也不相同.然而，不論一“輪”內(nèi)收到多少數(shù)據(jù)包，都是對整個區(qū)域的一次信息收集，獲得的信息量是相同的.于是，對于四種算法，我們都認為一“輪”內(nèi)BS節(jié)點收到的數(shù)據(jù)包是1.

圖6 一定能耗下BS收到的數(shù)據(jù)包

在圖6中，我們發(fā)現(xiàn)，在全網(wǎng)能量耗盡時，LEACH算法中，BS收到了1800個左右的數(shù)據(jù)包.BCDCP算法中，BS收到2000個左右的數(shù)據(jù)包，將效率提高了11%.GLIDND算法中，BS收到2200個左右的數(shù)據(jù)包，又將BCDCP算法的效率提高了10%.EEF算法中，BS收到2500個左右的數(shù)據(jù)包，略微提高了GLIDND算法的效率.Enhanced-GLIDND算法中，BS最后收到2700個左右的數(shù)據(jù)包，在能量有效性上明顯優(yōu)于其他算法.

Enhanced-GLIDND算法的另一個巨大優(yōu)勢：因為有大量備用節(jié)點集中在中心區(qū)域，在前1600“輪”左右，中心區(qū)域的簇頭節(jié)點即使因為能量耗盡而死亡也有足夠的備用節(jié)點，非中心區(qū)域的簇內(nèi)節(jié)點也基本沒有因為能量耗盡而死亡.所以，Enhanced-GLIDND算法中，BS在前1600“輪”左右收集到的是覆蓋范圍最全的信息.GLIDND算法備用節(jié)點在每“層”內(nèi)均勻分布，LEACH，BCDCP，EEF算法備用節(jié)點在整個區(qū)域均勻分布，于是，在200-400“輪”有多個節(jié)點死亡后，這幾種算法中，BS收集到的數(shù)據(jù)包所包含的信息往往都不能覆蓋整個區(qū)域.

4 結(jié)論

本文針對不同密度備用節(jié)點算法(GLIDND)的局限性，提出了一種改進的GLIDND算法Enhanced-GLIDND.仿真證明，與各經(jīng)典算法相比，新算法有效地減小了網(wǎng)絡(luò)平均能耗，延長了網(wǎng)絡(luò)生命周期，并提高了能量有效性.

[1]Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine,2002,(8),102-114.

[2]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[A]. Proceedings of the Hawaii International Conference on System Sciences[C]. San Francisco: IEEE Computer Society, 2000: 3005-3014.

[3]Muruganathan S D, Ma D C F, Bhasin R I, et al. A centralized energy-efficient routing protocol for wireless sensor networks[J]. IEEE Radio Communication,2005,(3): S8-13.

[4]Shen H. Finding the k most vital edges with respect to minimum spanning tree[A]. Proceedings of the IEEE National Aerospace and Electronics Conference[C]. 1997,(5):255-262.

[5]肖達. 一種基于地理位置的無線傳感器網(wǎng)絡(luò)路由節(jié)能算法研究[D]. 廈門：廈門大學(xué)碩士學(xué)位論文,2009.

[6]Xu Y, Heide J, Estrin D. Geography-informed energy conservation for ad hoc routing[A]. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking[C]. Rome, Italy: ACM, 2001:70-84.

[7]楊波. 基于蟻群算法的無線傳感器網(wǎng)絡(luò)路由算法研究[D]. 西安：西安電子科技大學(xué)碩士學(xué)位論文,2008.

[8]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機學(xué)報,2007,(1):27-36.

[9]李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進展[J].軟件學(xué)報,2003,(10):1717-1727.

[10]Kumar S, Kuila P, Jana P. Energy efficient routing algorithm for wireless sensor networks: A distributed approach[A].Proceedings of the International Conference on Communication and Computing Systems[C].2016:207-213.

AWirelessSensorNetworksRoutingProtocolBasedonGeographicalLocation

XIAO Da1, XIAO Mingbo2

(1. Hangzhou Technical Center, Nokia Solutions and Networks System Technology (Beijing) Co., Ltd, Hangzhou Zhejiang 310052, China; 2. College of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China)

In order to overcome the deficiencies of Different Nodes Density based on Geographical Location Information (GLIDND) algorithm in energy efficiency, this paper proposed an innovative Wireless Sensor Network (WSN) routing protocol Enhanced-GLIDND, which improves GLIDND in three aspects: (1) Sowing different density backup nodes at different location according to the energy consumption rate; (2) Choosing a new cluster head node by message notification scheme; (3)Selecting the next hop for a cluster head node by taking the accumulated energy consumption of the cluster in which the next hop cluster head is located as an influence factor. Simulation experiments evaluated Enhanced-GLIDND against EEF, GLIDND, LEACH and BCDCP, and the result shows that Enhanced-GLIDND outperforms any other algorithm in terms of the energy efficiency and the lifecycle of the whole network.

wireless sensor networks; different nodes density; cluster; lifecycle of network

TP393

A

1008-4681(2017)05-0024-09

2017-07-05

國家自然科學(xué)基金(批準(zhǔn)號：30900328)資助項目；杭州電子科技大學(xué)啟動基金(批準(zhǔn)號：KYS085612006)資助項目.

肖達(1983— )，男，江西上饒人，諾基亞通信系統(tǒng)技術(shù)(北京)有限公司杭州研發(fā)中心工程師，碩士.研究方向：物聯(lián)網(wǎng)、車輛自組織網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò).肖明波(1971— )，男，湖南沅江人，杭州電子科技大學(xué)通信工程學(xué)院教授，博士.研究方向：無線網(wǎng)絡(luò)資源管理與優(yōu)化、無線網(wǎng)絡(luò)跨層設(shè)計、QOS技術(shù)等.

(責(zé)任編校：晴川)