無(wú)線傳感器網(wǎng)絡(luò)PEGASIS協(xié)議的研究

李舒顏，李臘元

(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430063)

無(wú)線傳感器網(wǎng)絡(luò)被認(rèn)為是在一定空間范圍內(nèi)密集分布的由大量體積小、廉價(jià)、電池供電的通信器件構(gòu)成的自組織系統(tǒng)[1－2]。通常傳感器節(jié)點(diǎn)的電能非常有限，且電池是不可更換的，因此，傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題。而傳感器網(wǎng)絡(luò)路由協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地利用傳感器節(jié)點(diǎn)的能量，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。傳感器節(jié)點(diǎn)中消耗能量的模塊有傳感器模塊、處理器模塊和無(wú)線通信模塊等，其中無(wú)線通信消耗了大部分的能量[3]。研究表明，傳感器節(jié)點(diǎn)使用無(wú)線方式傳輸1 bit到100 m遠(yuǎn)所消耗的能量可供處理器模塊執(zhí)行3 000條指令[4]。由此可見，路由協(xié)議是影響傳感器網(wǎng)絡(luò)能耗的一個(gè)非常重要的因素。此外，傳感器節(jié)點(diǎn)采集的原始數(shù)據(jù)的數(shù)據(jù)量非常大，相鄰節(jié)點(diǎn)的信息具有很大的冗余性，因此，應(yīng)當(dāng)盡可能在本地進(jìn)行計(jì)算和數(shù)據(jù)融合，獲得有效信息，以減少信息的發(fā)送量。

1 研究現(xiàn)狀

按節(jié)點(diǎn)參與通信的方式，可以將無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議分為平面路由協(xié)議和分簇(clustering)路由協(xié)議[5]。平面路由協(xié)議的代表有 DD(directed diffusion)和 SPIN(sensor protocols for information via negotiation)等協(xié)議。由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量龐大，平面路由協(xié)議會(huì)導(dǎo)致網(wǎng)絡(luò)開銷較大，不利于網(wǎng)絡(luò)擴(kuò)展。分簇路由協(xié)議的代表有LEACH(low－energy adaptive clustering hierarchy)和PEGASIS(power－efficient gathering in sensor information system)等協(xié)議，這種路由協(xié)議的特點(diǎn)是將傳感節(jié)點(diǎn)分成不同的簇，簇內(nèi)成員節(jié)點(diǎn)將收集的數(shù)據(jù)信息都交給簇首(cluster head)，簇首通過數(shù)據(jù)融合減少傳輸信息量，最后把處理后的數(shù)據(jù)傳送給匯聚節(jié)點(diǎn)Sink(也有文獻(xiàn)稱為基站BS)。相比平面路由協(xié)議，分簇路由協(xié)議更能有效地控制拓?fù)?，網(wǎng)絡(luò)可擴(kuò)展性更優(yōu)，能量消耗更節(jié)省。

PEGASIS[6]協(xié)議是在LEACH協(xié)議基礎(chǔ)上發(fā)展而來(lái)的基于鏈的路由協(xié)議。其主要思想是:為了延長(zhǎng)網(wǎng)絡(luò)的生命周期，節(jié)點(diǎn)只需要與其最近的鄰居節(jié)點(diǎn)進(jìn)行通信。節(jié)點(diǎn)與匯聚點(diǎn)間的通信過程是輪流進(jìn)行的，當(dāng)所有節(jié)點(diǎn)都與匯聚點(diǎn)通信后，節(jié)點(diǎn)間再進(jìn)行新一輪回合。由于這種輪流通信機(jī)制使得能量消耗能夠統(tǒng)一地分布到每個(gè)節(jié)點(diǎn)上，因此可以降低整個(gè)傳輸所需要消耗的能量。雖然PEGASIS減小了LEACH在簇重構(gòu)過程中所產(chǎn)生的開銷，并且通過數(shù)據(jù)融合降低了收發(fā)過程的次數(shù)，從而降低了能量的消耗，但還存在以下幾個(gè)方面的問題[7]:①數(shù)據(jù)從鏈的遠(yuǎn)端傳輸?shù)芥準(zhǔn)坠?jié)點(diǎn)會(huì)引起過多的延遲，這對(duì)于很多對(duì)時(shí)延敏感的應(yīng)用場(chǎng)合來(lái)說(shuō)是不能接受的;②每個(gè)節(jié)點(diǎn)維護(hù)位置信息(相當(dāng)于傳統(tǒng)網(wǎng)絡(luò)中的拓?fù)湫畔?而產(chǎn)生額外的開銷;③協(xié)議所構(gòu)建的接鏈中，遠(yuǎn)距離的節(jié)點(diǎn)會(huì)引起過多的數(shù)據(jù)延遲，且鏈?zhǔn)坠?jié)點(diǎn)的唯一性使得鏈?zhǔn)讜?huì)成為瓶頸;④盡管協(xié)議避免了重構(gòu)簇的開銷，但由于傳感器節(jié)點(diǎn)需要知道鄰居的能量狀態(tài)以便傳送數(shù)據(jù)，協(xié)議仍需要?jiǎng)討B(tài)調(diào)整拓?fù)浣Y(jié)構(gòu)。對(duì)那些利用率高的網(wǎng)絡(luò)而言，拓?fù)涞恼{(diào)整會(huì)帶來(lái)更大的開銷。

正由于PEGASIS協(xié)議存在這些問題，從它被提出以來(lái)，國(guó)內(nèi)外學(xué)者對(duì)此開展了相關(guān)研究。文獻(xiàn)[8]提出了一種新的基于鏈狀網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)路由算法EB－PEGASIS。該算法通過已成鏈的平均距離獲得距離門限，利用距離門限避免長(zhǎng)鏈形成，可以保證形成數(shù)據(jù)鏈上節(jié)點(diǎn)發(fā)送數(shù)據(jù)消耗能量基本一致，避免部分節(jié)點(diǎn)因消耗能量較多而過早死亡。雖然該算法可以實(shí)現(xiàn)網(wǎng)絡(luò)壽命的延長(zhǎng)，但仍然沒有解決PEGASIS時(shí)延長(zhǎng)的問題。文獻(xiàn)[9]提出了一種被稱為COSEN的路由算法，通過設(shè)置參數(shù)CL限定每條鏈上節(jié)點(diǎn)的個(gè)數(shù)，在整個(gè)觀測(cè)區(qū)域構(gòu)造多條短鏈，并在每條鏈上固定選取一個(gè)節(jié)點(diǎn)作為簇頭，所有簇頭再構(gòu)成一條鏈與Sink通信，解決了PEGASIS協(xié)議中存在的時(shí)延過長(zhǎng)的問題，但在平衡節(jié)點(diǎn)能量消耗、簇頭節(jié)點(diǎn)的選擇等方面仍需要進(jìn)一步研究。

2 改進(jìn)的PEGASIS路由協(xié)議

2.1 傳感器網(wǎng)絡(luò)模型

考慮一個(gè)由N個(gè)隨機(jī)部署的傳感器節(jié)點(diǎn)形成的網(wǎng)絡(luò)，其應(yīng)用場(chǎng)景為周期性的數(shù)據(jù)收集。用si表示 i個(gè)節(jié)點(diǎn)，相應(yīng)的節(jié)點(diǎn)集合為 S={s1，s2，…，sn}，并基于以下假設(shè):①所有節(jié)點(diǎn)完全相同，均勻分布在一個(gè)正方形區(qū)域內(nèi)且靜止不動(dòng)，每個(gè)節(jié)點(diǎn)都可以與Sink直接通信;②信道是對(duì)稱的，且無(wú)線電信號(hào)在各個(gè)方向上能量消耗相同;③Sink節(jié)點(diǎn)是固定的，在網(wǎng)絡(luò)區(qū)域外并相距較遠(yuǎn);④節(jié)點(diǎn)間的通信采用廣播信道，若已知對(duì)方發(fā)射功率，節(jié)點(diǎn)可以根據(jù)接收信號(hào)的強(qiáng)度計(jì)算出發(fā)送者與自己的近似距離;⑤無(wú)線發(fā)射功率可控，即節(jié)點(diǎn)可以根據(jù)距離來(lái)調(diào)整發(fā)射功率的大小。

2.2 協(xié)議描述

2.2.1 節(jié)點(diǎn)區(qū)域劃分

在系統(tǒng)初始化階段，首先由Sink向觀測(cè)區(qū)域的所有節(jié)點(diǎn)發(fā)送分區(qū)消息，將整個(gè)觀察區(qū)域劃分成等寬的子區(qū)間，每個(gè)節(jié)點(diǎn)根據(jù)自己所在的位置確定區(qū)間ID號(hào)，并向Sink發(fā)送應(yīng)答信號(hào)，如圖1所示。具體的區(qū)域數(shù)和每一區(qū)域的節(jié)點(diǎn)數(shù)由Sink根據(jù)實(shí)際情況(如節(jié)點(diǎn)數(shù)量，區(qū)域大小，距離遠(yuǎn)近以及節(jié)點(diǎn)的密度等)修改區(qū)域?qū)挾鹊葏?shù)進(jìn)行設(shè)置。

圖1 層次區(qū)域劃分和構(gòu)造主鏈

2.2.2 節(jié)點(diǎn)鏈樹構(gòu)造

首先在每個(gè)區(qū)域中找出與Sink最近的節(jié)點(diǎn)，再在這些節(jié)點(diǎn)中從距離Sink最遠(yuǎn)的節(jié)點(diǎn)開始，采用貪婪算法構(gòu)造整個(gè)網(wǎng)絡(luò)的主鏈，各節(jié)點(diǎn)(已經(jīng)在鏈上的節(jié)點(diǎn)不再參與后續(xù)的成鏈過程)依次找到相鄰區(qū)域內(nèi)距離Sink最近的節(jié)點(diǎn)，該節(jié)點(diǎn)就作為鏈上的下一節(jié)點(diǎn)形成主鏈，如圖1所示。同時(shí)為了消除孤立節(jié)點(diǎn)的影響，當(dāng)某一節(jié)點(diǎn)與區(qū)域中的任一節(jié)點(diǎn)的通信距離都大于與Sink的距離時(shí)，則認(rèn)為該節(jié)點(diǎn)為孤立節(jié)點(diǎn)，孤立節(jié)點(diǎn)不參與到鏈中，而是直接與Sink進(jìn)行通信。接著再?gòu)拿總€(gè)區(qū)域中距離Sink最遠(yuǎn)的節(jié)點(diǎn)開始，找到與其最近的節(jié)點(diǎn)，作為自己的父節(jié)點(diǎn)加入到鏈上(已經(jīng)成為父節(jié)點(diǎn)的節(jié)點(diǎn)不再接受其他節(jié)點(diǎn)的請(qǐng)求)，然后再由新加入到鏈上的節(jié)點(diǎn)繼續(xù)尋找最近的節(jié)點(diǎn)重復(fù)此過程，最終形成多條并行的有向鏈連接到主鏈上，這樣整個(gè)網(wǎng)絡(luò)就構(gòu)成了如圖2所示的有序鏈樹。

圖2 鏈樹構(gòu)造和數(shù)據(jù)傳輸

2.2.3 根節(jié)點(diǎn)(鏈?zhǔn)坠?jié)點(diǎn))選擇

G－PEGASIS協(xié)議每一輪從主鏈上選擇一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)與Sink通信。由于觀測(cè)區(qū)域距離Sink較遠(yuǎn)，每輪擔(dān)任根節(jié)點(diǎn)的節(jié)點(diǎn)將會(huì)消耗比普通節(jié)點(diǎn)多得多的能量，此外，主鏈上的部分節(jié)點(diǎn)除了接收相鄰節(jié)點(diǎn)的數(shù)據(jù)外，還要接收與其連接的子鏈的數(shù)據(jù)，這樣主鏈上的節(jié)點(diǎn)比子鏈上的節(jié)點(diǎn)消耗的能量多。對(duì)此，除在首輪隨機(jī)選擇主鏈上任意一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)以外，其后由本輪的根節(jié)點(diǎn)確定自己的繼承人(下一輪的根節(jié)點(diǎn))。具體過程是當(dāng)主鏈上的節(jié)點(diǎn)向根節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，都附上自己的剩余能量信息報(bào)告給根節(jié)點(diǎn)，由當(dāng)前根節(jié)點(diǎn)指定剩余能量最多的節(jié)點(diǎn)擔(dān)任下一輪的根節(jié)點(diǎn)，這樣，與Sink直接通信的高負(fù)載就會(huì)平均到主鏈上的所有節(jié)點(diǎn)上。

2.2.4 數(shù)據(jù)傳輸

數(shù)據(jù)傳輸過程中，首先從每條子鏈的末梢節(jié)點(diǎn)開始并行向內(nèi)傳輸，節(jié)點(diǎn)調(diào)節(jié)到最小發(fā)射功率，將自己的數(shù)據(jù)傳向父節(jié)點(diǎn)，其父節(jié)點(diǎn)收到數(shù)據(jù)后與自己采集的數(shù)據(jù)進(jìn)行融合處理，再發(fā)往其父節(jié)點(diǎn)。這樣數(shù)據(jù)沿著每個(gè)區(qū)域中的子鏈傳輸，直到子鏈上的數(shù)據(jù)全部傳送到主鏈節(jié)點(diǎn)上。而后，主鏈再根據(jù)PEGASIS采用的數(shù)據(jù)傳輸方法，先由根節(jié)點(diǎn)產(chǎn)生Token，并將Token發(fā)往主鏈的任意一端，由該末端節(jié)點(diǎn)開始向其鄰居節(jié)點(diǎn)傳輸數(shù)據(jù)，同時(shí)令牌也交給鄰居節(jié)點(diǎn)，這樣數(shù)據(jù)經(jīng)逐次融合后就傳輸?shù)礁?jié)點(diǎn)上。然后根節(jié)點(diǎn)再將Token發(fā)往主鏈另外一端，重復(fù)同樣的過程。最后根節(jié)點(diǎn)將兩端傳來(lái)的數(shù)據(jù)經(jīng)過融合后，傳輸?shù)絊ink，整個(gè)過程如圖2所示。

2.3 能耗分析

根據(jù)如前所述的無(wú)線傳感網(wǎng)絡(luò)特點(diǎn)，對(duì)PEGASlS協(xié)議和G－PEGASIS協(xié)議能量模型作如下假設(shè):①網(wǎng)絡(luò)能量耗費(fèi)主要在數(shù)據(jù)發(fā)送、數(shù)據(jù)接收和數(shù)據(jù)融合這3個(gè)方面;②成鏈階段的能量耗費(fèi)相對(duì)整個(gè)數(shù)據(jù)傳送階段是很小的，可忽略不計(jì)。

而在實(shí)際中，由于接收機(jī)不接收數(shù)據(jù)時(shí)可關(guān)閉，因此接收機(jī)接收不是發(fā)給自己的數(shù)據(jù)的能量耗費(fèi)可不計(jì)。

筆者采用目前比較常用的傳感器節(jié)點(diǎn)工作能耗模型[10]，將一k b的信息傳送距離d，無(wú)線通信模塊的發(fā)送能耗和接收能耗分別為:

融合k b的數(shù)據(jù)信息所耗費(fèi)的能量為:Eagg(k，d)=Eaggo。

式中:Eelec為傳感器無(wú)線發(fā)射電路(TE)或無(wú)線接收電路(RE)發(fā)送或接收每 bit的能耗;ETx－elec(k)、ETx－amp(k，d)、ERx－elec(k)分別為發(fā)射電路、發(fā)射電路放大器和接收電路的能耗;εamp為發(fā)射放大器將每bit傳送單位m2所耗的能量。

在PEGASIS協(xié)議中，n個(gè)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)沿著鏈傳輸k b的數(shù)據(jù)到鏈?zhǔn)坠?jié)點(diǎn)所消耗的能量為:

式中:d(i，j)為鏈上兩個(gè)節(jié)點(diǎn)ni到nj的通信距離。從末梢節(jié)點(diǎn)到鏈?zhǔn)坠?jié)點(diǎn)數(shù)據(jù)融合消耗的能量為:

式中，Eagg為節(jié)點(diǎn)融合每bit數(shù)據(jù)的能耗。

在改進(jìn)的PEGASIS協(xié)議，即G－PEGASIS協(xié)議中，設(shè)有m條子鏈，則末梢節(jié)點(diǎn)比PEGASIS協(xié)議多m個(gè)，這m個(gè)末梢節(jié)點(diǎn)可以少消耗接收和融合數(shù)據(jù)的能量為mEeIeck+mEaggk，但是主鏈上會(huì)有m個(gè)節(jié)點(diǎn)，除了接收主鏈上的數(shù)據(jù)外，其額外消耗接收和融合子鏈節(jié)點(diǎn)的能量也為mEeleck+mEaggk，因此，G－PEGASIS協(xié)議在所有節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)礁?jié)點(diǎn)階段消耗的能量就與PEGASIS協(xié)議相等。

在G－PEGASIS協(xié)議中，每個(gè)子區(qū)域內(nèi)距離Sink節(jié)點(diǎn)最近的節(jié)點(diǎn)為鏈?zhǔn)坠?jié)點(diǎn)，其與Sink的距離為L(zhǎng)i1，主鏈節(jié)點(diǎn)以外的節(jié)點(diǎn)與Sink的距離為L(zhǎng)ij;而在PEGASIS協(xié)議中，鏈?zhǔn)坠?jié)點(diǎn)在整個(gè)監(jiān)測(cè)區(qū)域中產(chǎn)生，當(dāng)每個(gè)區(qū)域中主鏈節(jié)點(diǎn)以外的節(jié)點(diǎn)被選擇為鏈?zhǔn)坠?jié)點(diǎn)時(shí)，其與Sink的距離Lij＞Li1，則消耗的能量這樣在經(jīng)過若干輪后，PEGASIS協(xié)議中鏈?zhǔn)坠?jié)點(diǎn)與Sink通信所消耗的能量就會(huì)大于G－PEGASISI協(xié)議所消耗的能量。由于在G－PEGASIS協(xié)議中數(shù)據(jù)在子鏈上是并行傳輸?shù)?，這樣可以有效減小數(shù)據(jù)傳輸延遲。此外，在PEGASIS協(xié)議中，當(dāng)有節(jié)點(diǎn)失效時(shí)，則會(huì)重構(gòu)鏈;而在G－PEGASISI協(xié)議中，當(dāng)主鏈和子鏈上有節(jié)點(diǎn)失效后，整個(gè)網(wǎng)絡(luò)不會(huì)重構(gòu)鏈樹，而是屏蔽掉失效節(jié)點(diǎn)，由該失效節(jié)點(diǎn)的兩相鄰節(jié)點(diǎn)直接進(jìn)行通信。只有當(dāng)各區(qū)域中離Sink最近的節(jié)點(diǎn)全部失效后，才會(huì)重新構(gòu)造主鏈，且依然由各區(qū)域中與Sink距離最近的節(jié)點(diǎn)擔(dān)任鏈?zhǔn)坠?jié)點(diǎn)，繼續(xù)與Sink通信。

3 模擬實(shí)驗(yàn)及分析

模擬實(shí)驗(yàn)采用由UC Berkley大學(xué)研發(fā)的事件驅(qū)動(dòng)和面向?qū)ο蟮木W(wǎng)絡(luò)仿真工具NS2，場(chǎng)景相關(guān)參數(shù)設(shè)置如表1所示。整個(gè)區(qū)域劃分為5個(gè)部分，每個(gè)部分中的節(jié)點(diǎn)數(shù)為20個(gè)，所有節(jié)點(diǎn)一旦放置就不能再移動(dòng)。節(jié)點(diǎn)死亡只發(fā)生在能量為零時(shí)。模擬運(yùn)行期間，采用網(wǎng)絡(luò)生存周期作為算法節(jié)能的評(píng)價(jià)指標(biāo)。圖3為兩種協(xié)議網(wǎng)絡(luò)生存時(shí)間的比較，G－PEGASIS協(xié)議在第一個(gè)節(jié)點(diǎn)死亡和全部節(jié)點(diǎn)死亡的輪次上比PEGASIS協(xié)議有所延長(zhǎng)。從圖3可以看出，G－PEGASIS協(xié)議的網(wǎng)絡(luò)生存時(shí)間比PEGASIS協(xié)議長(zhǎng)13%以上。

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

圖3 兩種協(xié)議網(wǎng)絡(luò)生存時(shí)間的對(duì)比

圖4為節(jié)點(diǎn)總的能量消耗對(duì)比，分層鏈樹協(xié)議中節(jié)點(diǎn)能量消耗總和小于PEGASIS協(xié)議。

圖4 節(jié)點(diǎn)總的能量消耗對(duì)比

4 結(jié)論

筆者在對(duì)PEGASIS協(xié)議進(jìn)行深入分析的基礎(chǔ)上，指出了其局限性，并有針對(duì)性地提出了改進(jìn)后的G－PEGASIS協(xié)議。該協(xié)議通過將觀測(cè)區(qū)域劃分為等寬的子區(qū)間，然后根據(jù)與Sink通信距離的遠(yuǎn)近，找出每個(gè)子鏈中距離Sink最近的節(jié)點(diǎn)，建立主鏈，同時(shí)采取多條子鏈并行前向傳輸?shù)姆椒?，?jié)省了網(wǎng)絡(luò)的能耗，平衡了節(jié)點(diǎn)負(fù)載，減小了網(wǎng)絡(luò)時(shí)延。實(shí)驗(yàn)結(jié)果表明，G－PEGASIS協(xié)議在生存時(shí)間、能耗均衡等方面的性能比PEGASIS協(xié)議有明顯改進(jìn)。

[1] AKULDIZ F，SU W，SANKARASUBRAMANIAN Y，et al.A survey of sensor networks[J].IEEE Communications Magazine，2002，40(8):102 －144.

[2] 李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及數(shù)據(jù)管理的概念、問題與發(fā)展[J].軟件學(xué)報(bào)，2003，14(10):1717－1727.

[3] 孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2005:9－14.

[4] ESTRIN D.Wireless sensor networks tutorial part IV:sensor network protocols[M].Atlanta:Mobicom，2002:23－28.

[5] 周琴，李臘元.基于雙簇頭的無(wú)線傳感器網(wǎng)絡(luò)多跳路由協(xié)議[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2010，32(4):202 －205.

[6] LINDSEY S，RAGHAVENDRA C，SIVALINGAM K M.Data gathering algorithms in sensor networks using energy metrics[J].IEEE Transactions on Parallel and Distributed Systems，2002，13(9):350 －354.

[7] IBRIQ J，MAHGOUB I.Cluster － based routing in wireless sensor networks:issue and challenge[C]//Proceedings of the 2004 Symposium on Performance Evaluation of Computer Telecommunication Systems.Alifornia:[s.n.]，2004:759－766.

[8] LIU Y Y，JI H，YUE G X.An energy efficient PEGASIS based enhanced algorithm in wireless sensor networks[J].China Communications，2006，6(3):91 －97.

[9] TABASSUM N，EHSANUL Q，MAMUN K，et al.COSEN:a chain oriented sensor network for efficient data collection[M].Las Vegas:[s.n.]，2006:262 －267.

[10] WANG A，HEINZELMAN W B，SINHA A ，et al.Energy scalable protocols for battery－operated microsensor networks[J].Journal of VLSI Signal Processing，2001，29(3):223－237.