許東菊 鄭明春

山東師范大學(xué)管理科學(xué)與工程學(xué)院 山東 250014

0 引言

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

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

1 相關(guān)工作

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

2 LEACH算法改進(jìn)的新算法

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

2.1 模型描述

在特定的區(qū)域內(nèi)，N個(gè)無(wú)線傳感器節(jié)點(diǎn)隨機(jī)均勻分布，周期性收集周?chē)h(huán)境的信息，并具有如下一些性質(zhì)：

假設(shè)所有的傳感器節(jié)點(diǎn)一經(jīng)部署后都是靜止不動(dòng)的，且每一個(gè)節(jié)點(diǎn)都有惟一的一個(gè)預(yù)先分配的標(biāo)識(shí)ID。

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

假設(shè)鏈路是對(duì)稱(chēng)的。

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

接收l(shuí)bit數(shù)據(jù)消耗的能量為：

2.2 算法描述

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

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

2.2.1 AECRA簇的建立

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

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

圖1 臨時(shí)簇的建立

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

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

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

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

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

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

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

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

表2 路由信息表

3 仿真實(shí)驗(yàn)和性能分析

到此從簇首節(jié)點(diǎn)到Sink節(jié)點(diǎn)的最小“費(fèi)用”路由樹(shù)建成。

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[2] 蔡紹濱.無(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究與應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版社.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ú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社.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] 劉瓊，成運(yùn).一種無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].現(xiàn)代電子技術(shù).2010.

[9] 劉鐵流，巫詠群.基于能量?jī)?yōu)化的無(wú)線傳感器分簇路由算法研究[J].傳感器技術(shù)學(xué)報(bào).2011.

[10] 黃海軍.城市交通網(wǎng)絡(luò)平衡分析-理論與實(shí)踐[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.