一種基于地理位置的無線傳感器網絡路由算法

肖 達,肖明波

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

一種基于地理位置的無線傳感器網絡路由算法

肖 達1,肖明波2

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

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

無線傳感器網絡；不同節點密度；簇；網絡生命周期

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

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

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

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

1 GLIDND路由算法

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

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

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

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

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

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

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

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

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

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

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

在每“輪”循環中，當簇頭、簇頭多跳路徑以及TDMA調度均確定下來之后，節點便可以進行數據傳輸了.簇內的成員節點根據TDMA調度，在自己所在時隙內向簇頭發送數據，簇頭按照多跳路徑的方向發送數據，直至將數據發送給BS節點.

2 改進的GLIDND算法

2.1傳感區域的劃分

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

圖1 Enhanced-GLIDND算法拓撲圖

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

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

(1)

圖2 傳輸距離的設定

接下來我們將說明劃分出多少個區域數才能達到能量的最優利用，以及如何在不同區域撒布不同密度的備用節點.

2.2最優區域個數和不同區域備用節點密度的確定

將目標區域劃分成一個個小的邏輯區域可以縮小數據通信距離，提高能效.同時各個區域并行運行成簇算法，也使網絡響應速度得以提高.但是，區域數量的多少直接影響簇的數量和大小，根據目標區域面積、節點數量等參數來優化區域數量是提高系統整體性能的必然要求.

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

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

Ech=

(2)

=

式中：

Eelec：發送電路和接收電路消耗的能量；

EDA：節點進行數據融合消耗的能量；

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

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

dCH-CH:簇頭節點間距；

dtoBS: 簇頭節點到基站的距離；

M：區域邊長；

N：節點個數；

m：最優“層”數；

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

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

(3)

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

(4)

圖3 單個簇內節點分布

因此，一個簇內的能耗為

(5)

令Ecluster=

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

(6)

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

因為每一“層”有m個簇，于是，在監測區域(level

于是，系統總能耗

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

(7)

(8)

(9)

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

表1 一“輪”內各節點的能耗

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

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

(10)

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

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

(11)

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

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

2.3.1 確立簇頭

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

首輪：

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

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

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

步驟 4：這一步是成簇最后的關鍵一步.本算法采用同LEACH算法一樣的TDMA機制，簇頭節點給每個簇內節點分配一個時間片，節點會按照時間片的先后順序來發送數據給簇頭.

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

第二“輪”后：

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

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

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

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

2.3.2 簇頭多跳路徑階段

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

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

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

(12)

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

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

(13)

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

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

(14)

式中，N表示下一跳的可選區域.

3 仿真試驗

3.1仿真環境

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

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

表2 仿真參數設置

3.2結果分析

3.2.1 平均能量消耗

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

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

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

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

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

3.2.2 存活節點個數

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

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

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

3.2.3 能量有效性

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

圖6 一定能耗下BS收到的數據包

在圖6中，我們發現，在全網能量耗盡時，LEACH算法中，BS收到了1800個左右的數據包.BCDCP算法中，BS收到2000個左右的數據包，將效率提高了11%.GLIDND算法中，BS收到2200個左右的數據包，又將BCDCP算法的效率提高了10%.EEF算法中，BS收到2500個左右的數據包，略微提高了GLIDND算法的效率.Enhanced-GLIDND算法中，BS最后收到2700個左右的數據包，在能量有效性上明顯優于其他算法.

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

4 結論

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

[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]肖達. 一種基于地理位置的無線傳感器網絡路由節能算法研究[D]. 廈門：廈門大學碩士學位論文,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]楊波. 基于蟻群算法的無線傳感器網絡路由算法研究[D]. 西安：西安電子科技大學碩士學位論文,2008.

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

[9]李建中,李金寶,石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報,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

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

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

(責任編校：晴川)