無線傳感器網(wǎng)絡(luò)分簇路由算法研究與改進

許東菊 鄭明春

山東師范大學管理科學與工程學院 山東 250014

0 引言

無線傳感器網(wǎng)絡(luò)就是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息，并發(fā)送給觀察者。一個傳感器節(jié)點由傳感器模塊、處理器模塊、無線通信模塊和能量供應(yīng)模塊四部分組成，其中能量供應(yīng)模塊提供傳感器節(jié)點運行所需的能量，它通常采用能量有限的微型電池供電，因此如何提高電池能量的利用率，延長網(wǎng)絡(luò)壽命，成為近年來研究的熱點。

在分簇路由算法中，網(wǎng)絡(luò)通常被劃分為簇(Cluster)。簇，即具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點集合。每一個簇由一個簇首(Cluster Head)和多個簇內(nèi)成員(Cluster Member)組成。分簇式的層次型拓撲結(jié)構(gòu)具有很多優(yōu)點：數(shù)據(jù)融合主要是由簇頭節(jié)點來承擔，減少了數(shù)據(jù)通信量；采用分簇式的拓撲結(jié)構(gòu)有利于應(yīng)用分布式算法，適合大規(guī)模的網(wǎng)絡(luò)；成員節(jié)點大部分時間可以關(guān)閉通信模塊，由簇首構(gòu)成一個更上一層的連通網(wǎng)絡(luò)來負責數(shù)據(jù)的長距離路由轉(zhuǎn)發(fā)，可以顯著地延長網(wǎng)絡(luò)壽命；便于擴展和管理，并能夠很好地解決傳感器節(jié)點移動帶來的定位問題。本文提出的路由算法，正是考慮了分簇的層次拓撲結(jié)構(gòu)的這些優(yōu)點，采用了新的簇首選擇方法，同時構(gòu)造簇間多跳路由，利用Wardrop均衡原理，選擇“費用”最少的路徑傳輸數(shù)據(jù)到Sink節(jié)點，從而進一步降低能量消耗，延長整個網(wǎng)絡(luò)的壽命。

1 相關(guān)工作

在傳感器網(wǎng)絡(luò)中，傳感器節(jié)點的無線通信模塊在空閑時的能量消耗與在收發(fā)狀態(tài)時相當，所以只有關(guān)閉節(jié)點的無線通信模塊，才能大幅度的降低節(jié)點的能量開銷。層次型拓撲結(jié)構(gòu)的分簇算法將節(jié)點劃分為簇首節(jié)點和普通節(jié)點，通過采取一定的機制選擇某些節(jié)點為簇首節(jié)點，打開簇首節(jié)點的無線通信模塊，并關(guān)閉普通節(jié)點的通信模塊，由簇首節(jié)點構(gòu)建一個連通網(wǎng)絡(luò)來負責數(shù)據(jù)的路由轉(zhuǎn)發(fā)。這樣既能保證全網(wǎng)內(nèi)的數(shù)據(jù)通信，又在很大程度上節(jié)省了節(jié)點的能量。由于簇首節(jié)點需要負責簇內(nèi)節(jié)點數(shù)據(jù)的融合和轉(zhuǎn)發(fā)，能量消耗較大，所以周期性的選擇簇首，可以避免某些節(jié)點由于能量消耗過快而很快死亡，從而均衡網(wǎng)絡(luò)節(jié)點的能量消耗。

2 LEACH算法改進的新算法

近年來，針對LEACH協(xié)議的改進主要表現(xiàn)在兩個方面：(1)簇頭的選擇；(2)簇間采用多跳通信方式傳輸數(shù)據(jù)到Sink節(jié)點。本文正是從這兩個方面對LEACH協(xié)議進行改進，設(shè)計一種基于分簇的高效路由算法(An Efficient Cluster-based Routing Algorithm，AECRA)，其基本思想是：在考慮節(jié)點的剩余能量和相鄰節(jié)點間的能量消耗的基礎(chǔ)上選擇簇首節(jié)點；簇首節(jié)點確定以后，利用貪婪算法結(jié)合Wardrop均衡原理，選擇簇首節(jié)點到Sink節(jié)點“費用”最少路徑傳輸數(shù)據(jù)，降低整體能量消耗，延長網(wǎng)絡(luò)壽命。

2.1 模型描述

在特定的區(qū)域內(nèi)，N個無線傳感器節(jié)點隨機均勻分布，周期性收集周圍環(huán)境的信息，并具有如下一些性質(zhì)：

假設(shè)所有的傳感器節(jié)點一經(jīng)部署后都是靜止不動的，且每一個節(jié)點都有惟一的一個預先分配的標識ID。

假設(shè)只考慮單一的Sink節(jié)點，且Sink節(jié)點的能量不受限制假設(shè)節(jié)點可以根據(jù)接收方距離的遠近自動調(diào)節(jié)發(fā)射功率。

假設(shè)鏈路是對稱的。

AECRA算法采用和LEACH算法相同的無線通信模型，當節(jié)點傳輸lbit數(shù)據(jù)到距離為d的節(jié)點所消耗的能量為：

接收lbit數(shù)據(jù)消耗的能量為：

2.2 算法描述

同LEACH算法一樣，AECRA算法也是按輪進行的。當節(jié)點隨機部署完成以后，首先要做的就是尋找鄰居節(jié)點，并建立一個鄰居列表，存儲鄰居節(jié)點惟一的 ID及節(jié)點的一些特性，如果某個節(jié)點的能量耗盡，它的 ID將從鄰居列表中移除(見表1)。

表1 鄰居表內(nèi)容

2.2.1 AECRA簇的建立

在隨機部署節(jié)點之前，預先定義一個初始能量閥值，嵌入到每一個節(jié)點中。在這里我們采用網(wǎng)絡(luò)中存活節(jié)點的剩余能量的平均值作為初始能量閥值。在整個網(wǎng)絡(luò)生命周期內(nèi)，Sink節(jié)點可以決定剩余能量閥值，并在每一輪開始時，它都是可以改變的。簇頭節(jié)點收集簇內(nèi)節(jié)點的剩余能量值，并把所有節(jié)點的剩余能量的平均值發(fā)給Sink節(jié)點，Sink節(jié)點計算整個網(wǎng)絡(luò)剩余能量平均值并告知每一個簇頭節(jié)點，簇內(nèi)節(jié)點通過和其簇頭節(jié)點進行直接通信，獲得新的能量閥值。

如果一個節(jié)點剩余能量大于初始能量閥值，并且沒有收到來自其它節(jié)點宣布為臨時簇頭的公告信息，則宣布自己為臨時簇頭，并告知它的鄰居節(jié)點。同時，收到臨時簇頭公告信息的鄰居節(jié)點，需要把自己的剩余能量和 ID反饋給臨時簇頭。如果一些節(jié)點同時收到多個臨時簇頭的公告信息，它只回復和它相鄰最近的臨時簇頭。這樣就建立了臨時簇。臨時簇的建立過程(見圖1)。

圖1 臨時簇的建立

在每一個臨時簇中，簇內(nèi)成員節(jié)點具有較高剩余能量的可以作為潛在的簇頭節(jié)點，并告知臨時簇頭。臨時簇頭和潛在簇頭節(jié)點通過對比節(jié)點剩余能量同鄰居節(jié)點的平均能耗的比值，確定最終的簇頭節(jié)點。

進入穩(wěn)定的運行階段后，簇內(nèi)節(jié)點持續(xù)的檢測、采集數(shù)據(jù)，傳給簇頭節(jié)點后發(fā)送給Sink節(jié)點，持續(xù)一段時間后，進入下一個周期，重新選擇簇頭。

2.2.2 AECRA簇間動態(tài)多跳路由算法

該算法對簇首節(jié)點和 Sink節(jié)點的通信方式做進一步的改進，采用多跳方式，建立由簇首節(jié)點組成，以Sink節(jié)點為根的樹。

為了確保從簇首節(jié)點到 Sink節(jié)點之間的路徑是最優(yōu)路徑，本文以泛洪(flooding)方式作為路由樹的生成方式，具體過程如下：

(1) 定義Sink節(jié)點深度為0，距離Sink一跳的簇首節(jié)點的深度為1，依此類推，Sink節(jié)點用泛洪的方式確定第i簇首節(jié)點到Sink節(jié)點的深度di；

(2) 從深度為0的Sink節(jié)點開始，各節(jié)點逐次向其相鄰的深度為di+1的鄰居節(jié)點通報數(shù)據(jù)包傳輸?shù)絊ink節(jié)點的最優(yōu)費用pi，其中Pi表示從i節(jié)點到Sink節(jié)點的最小的“費用”路由的總費用；Eij表示從i節(jié)點到相鄰節(jié)點j的能量消耗。

(3) 第i簇首節(jié)點收到上一深度相鄰簇首節(jié)點j、k傳送的節(jié)點信息后，為每個相鄰簇首節(jié)點建立路由信息表(見表2)。換為較容易計算的弧流量引入到模型中，并用較為簡單的“全有全無”方法進行求解，本文也將應(yīng)用該方法求解。

表2 路由信息表

3 仿真實驗和性能分析

到此從簇首節(jié)點到Sink節(jié)點的最小“費用”路由樹建成。

算法開始時，Sink先以給定的功率向全網(wǎng)發(fā)送廣播信號，節(jié)點根據(jù)收到的信號的強弱計算出它到Sink節(jié)點的距離d。并假定中繼簇頭收到上一跳的數(shù)據(jù)沒有冗余信息，且來自不同簇的數(shù)據(jù)無法進一步融合，中繼簇頭只是簡單的轉(zhuǎn)發(fā)來自其他簇頭的數(shù)據(jù)。簇首節(jié)點通過公式(1)計算得到它直接傳送數(shù)據(jù)到Sink節(jié)點的能量消耗，標記為Etosink；只有滿足通過中繼轉(zhuǎn)發(fā)的費用P＜Etosink，簇首節(jié)點才會選擇通過多跳方式。由于在每個周期內(nèi)，每個簇首節(jié)點都是自私的尋找一條“費用”最少路徑，這就導致某些節(jié)點的能量消耗過快，后繼數(shù)據(jù)包在傳送時就會選擇一些能耗下降較少的次優(yōu)路徑傳送，經(jīng)過一段時間，可認為數(shù)據(jù)流會根據(jù)路由選擇機制均勻的分配到不同的路徑上，達到一種均衡狀態(tài)，即 Wardrop均衡，在這種均衡狀態(tài)下，每一個簇首節(jié)點都認為自己采取了最優(yōu)的路由策略，本文中我們應(yīng)用文獻[10]中的模型求解這種最優(yōu)的路由策略，實現(xiàn)整個網(wǎng)絡(luò)的傳輸“總費用”最小，模型描述如下：

定義數(shù)據(jù)傳輸過程中鏈路(1跳)的“費用”函數(shù)為：

本文利用 NS-2仿真平臺對 LEACH、LEACH-C和AECRA算法進行仿真比較，在100m×100m的矩形區(qū)域內(nèi)隨機部署 100個傳感器節(jié)點，Sink節(jié)點位于(50,175)，所有節(jié)點的通信距離為20m，節(jié)點的初始能量E0=2J，原始數(shù)據(jù)產(chǎn)生速率為1kb/s，發(fā)射電路和接收電路需要消耗的能量ETX=ERX=50nJ/bit，簇頭融合數(shù)據(jù)消耗的能量Edf=50pJ/bit ，功率放大器消耗的能量Efs=100pJ/(bit?d-2)，信號放大器倍數(shù)εmp=0.0013pJ/bit/m4，采樣周期為10s，簇頭個數(shù)Kopt=5，節(jié)點能量為0時，認為節(jié)點死亡，并且假定數(shù)據(jù)融合率為 100%，在轉(zhuǎn)發(fā)過程中不存在數(shù)據(jù)包丟失，無誤碼率。

圖 2是存活節(jié)點數(shù)和輪數(shù)關(guān)系圖?？梢钥闯?，LEACH協(xié)議的曲線下降比較快，網(wǎng)絡(luò)中節(jié)點能量消耗大，LEACH-C協(xié)議曲線在300輪前節(jié)點能量消耗比LEACH大，但是之后存活節(jié)點個數(shù)多于 LEACH，且整個網(wǎng)絡(luò)的生命周期明顯比LEACH長。這是由于LEACH-C在每輪循環(huán)中，節(jié)點都要向Sink節(jié)點發(fā)送自己的位置和剩余能量，所以剛開始時節(jié)點能量消耗比LEACH大，但是由于LEACH-C是Sink節(jié)點合理的選取簇頭，所以運行一段時間后，存活節(jié)點的個數(shù)多于LEACH。而AECRA算法由于考慮了解點的剩余能量和簇頭節(jié)點間采用多跳的方式傳輸數(shù)據(jù)，所以在每輪循環(huán)中存活節(jié)點的個數(shù)明顯優(yōu)于LEACH和LEACH-C，從而延長了整個網(wǎng)絡(luò)的生存周期。

其中A為所有鏈路的集合。

可以證明，模型的一階必要條件滿足本文提出的路由選擇方式。直接求解該模型是非常困難的，針對這類問題，Backmann提出Frank-Wolf方法，將難以計算的路徑流量轉(zhuǎn)

圖2 存活節(jié)點數(shù)和輪數(shù)關(guān)系圖

圖3是節(jié)點能耗和輪數(shù)關(guān)系圖，顯示的節(jié)點的總的能量消耗情況，仿真實驗中每隔 10輪做 1次采樣記錄。從圖 3可以看出，新算法的節(jié)點總能量消耗少于LEACH算法，說明新算法有效的節(jié)省了能量，延長整個網(wǎng)絡(luò)壽命。

圖3 節(jié)點能耗和輪數(shù)關(guān)系圖

4 結(jié)束語

本文提出一種基于能量和距離的分簇多跳路由算法-AECRA算法，簇頭的選擇考慮了節(jié)點的剩余能量和相鄰節(jié)點間的能量消耗，并且改進了簇頭和Sink節(jié)點間通信的方式，應(yīng)用Wardrop均衡原理尋找最優(yōu)路由策略進行數(shù)據(jù)轉(zhuǎn)發(fā)。仿真結(jié)果表明，與LEACH算法和LEACH-C算法相比較，新算法有效的節(jié)省了節(jié)點的能耗，延長了整個網(wǎng)絡(luò)的生存周期。

[1] 邱天爽,唐洪等譯.無線傳感器網(wǎng)絡(luò)協(xié)議與體系結(jié)構(gòu)[M].北京:電子工業(yè)出版社.2007.

[2] 蔡紹濱.無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究與應(yīng)用[M].哈爾濱工業(yè)大學出版社.2011.

[3] Heinzelman W, Chandrakasan A, Balakrishnan H.Energy-Efficient communication protocol for wireless microsensor networks[R].In:Proc. of the 33rd Annual Hawaii Int’l Conf. on System Sciences.Maui: IEEE Computer Society.2000.

[4] 孫利民,李建中等著.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社.2011.

[5] Younis O, Fahmy S. Heed: A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks[J]. IEEE Trans. on Mobile Computing, 2004.

[6] Heinzelman W R,Chandrakasan A,Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Micro-Sensor Networks［J.IEEE Transaction on Wireless Communications.2002.

[7] Tillapart P, Thumthawatworn T,Pakdeepinit P,Yeophantong T,Charoenvikrom S,Daengdej J.Method for cluster heads selection in wireless sensor networks[R].In:Proc.of the 2004 IEEE Aerospace Conf. Chiang Mai: IEEE Press.2004.

[8] 劉瓊，成運.一種無線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].現(xiàn)代電子技術(shù).2010.

[9] 劉鐵流，巫詠群.基于能量優(yōu)化的無線傳感器分簇路由算法研究[J].傳感器技術(shù)學報.2011.

[10] 黃海軍.城市交通網(wǎng)絡(luò)平衡分析-理論與實踐[M].北京:人民交通出版社.1994.

[11] Beckmann M,Mcguire CB,Winsten CB.Studies in the Economics of Transportation[M].New Haven: Yale University Press.1955.

[12] Yuan YX,Sun WY.Optimization Theory and Methods[M].Beijing:Science Press.1997.