WSN中一種基于延遲限定的數(shù)據(jù)收集算法

趙 通

(武漢理工大學(xué)信息工程學(xué)院，湖北武漢430070)

0 引言

綜合了無線通信技術(shù)、傳感器技術(shù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是目前國(guó)際上前沿?zé)狳c(diǎn)的研究領(lǐng)域。傳感器節(jié)點(diǎn)能夠協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知網(wǎng)絡(luò)區(qū)域內(nèi)各種信息，然后以多跳的方式將這些信息傳送給遠(yuǎn)方的基站(Sink)［1］。在一些持續(xù)性的監(jiān)視應(yīng)用中，如:森林火警監(jiān)視、礦道瓦斯監(jiān)測(cè)和戰(zhàn)場(chǎng)監(jiān)控等，不僅要求網(wǎng)絡(luò)能保存能量長(zhǎng)期地工作，還要求網(wǎng)絡(luò)在收集到數(shù)據(jù)后能盡快地將數(shù)據(jù)傳送給用戶進(jìn)行處理，即網(wǎng)絡(luò)需要滿足最大化生命周期和最小延遲這2個(gè)要求。下面針對(duì)該問題進(jìn)行研究。

1 相關(guān)工作

目前有很多工作分別研究網(wǎng)絡(luò)生命周期最大以及傳輸延遲最小的數(shù)據(jù)收集協(xié)議，以達(dá)到目標(biāo)的方式進(jìn)行劃分，主要有以下3類:① 功率控制。就是為傳感器節(jié)點(diǎn)選擇合適的發(fā)射功率。比較典型的協(xié)議有:拓?fù)淇刂凭S護(hù)網(wǎng)絡(luò)連接(TCMNC)［2］和能量與延遲協(xié)議(TOED)［3］等。②睡眠調(diào)度。就是控制傳感器節(jié)點(diǎn)在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換。比較典型協(xié)議有:延遲敏感的壽命最大化(MLDS)［4］和最小能量消耗(MEC)［5］。睡眠調(diào)度能使冗余節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)，大幅度地降低網(wǎng)絡(luò)的能量消耗和競(jìng)爭(zhēng)信道沖突，這對(duì)于節(jié)點(diǎn)密集型和事件驅(qū)動(dòng)型的網(wǎng)絡(luò)十分有效。但它需要在保證網(wǎng)絡(luò)覆蓋的情況下構(gòu)造最優(yōu)的連通支配集，這也是一個(gè)NP完全的問題。③拓?fù)渖?。就是將?jié)點(diǎn)按一定方式組織起來，協(xié)作地傳輸數(shù)據(jù)。比較典型的協(xié)議有基于簇的協(xié)議、基于鏈的協(xié)議和基于樹的協(xié)議更迭逼近算法(IAA)［6］、延遲限定 － 最小生成樹(DB-MDST)［7］等。其中基于樹的協(xié)議經(jīng)常被用于在持續(xù)性的監(jiān)視應(yīng)用中進(jìn)行數(shù)據(jù)收集，是目前研究的熱點(diǎn)。然而，IAA和DB－MDST等在構(gòu)造生成樹的過程中，樹外節(jié)點(diǎn)是作為葉子節(jié)點(diǎn)被考慮并加入樹的，在樹沒有最終建立前無法確定一個(gè)節(jié)點(diǎn)最終在樹上擁有多少孩子。因此它們的生成樹往往存在節(jié)點(diǎn)負(fù)載不均衡、樹的高度無法控制的情況，這樣不利于最大化樹的生命周期，而且容易導(dǎo)致很大的延遲。在前人研究的基礎(chǔ)上，提出了一個(gè)新的算法——DBDG，來構(gòu)造一顆限定高度、負(fù)載均衡的生成樹，從而有效滿足延遲限定和網(wǎng)絡(luò)生命周期最大化的要求。最后的仿真實(shí)驗(yàn)也驗(yàn)證了本文方法的有效性。

2 系統(tǒng)模型和問題描述

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

n個(gè)傳感器節(jié)點(diǎn)隨機(jī)地分布在一個(gè)面積為M×M m2的正方形區(qū)域A內(nèi)，存在1個(gè)Sink節(jié)點(diǎn)。整個(gè)傳感器網(wǎng)絡(luò)組成一個(gè)連通的無向圖G(V，E)，其中V是節(jié)點(diǎn)集合，V={v0，v1，v2，…，vn}，|V|=n+1，其中v0是 Sink 節(jié)點(diǎn)，v1，v2，…，vn是傳感器節(jié)點(diǎn);E 是 G 中邊的集合，如果2個(gè)傳感器節(jié)點(diǎn)vi和vj相互處于對(duì)方的通信半徑內(nèi)，則(vi，vj)∈E。|E|=m為邊的數(shù)量。網(wǎng)絡(luò)具有如下性質(zhì):①網(wǎng)絡(luò)是連通的靜態(tài)網(wǎng)絡(luò)，節(jié)點(diǎn)部署后不再移動(dòng);② 傳感器節(jié)點(diǎn)的種類可以有多種，它們的初始能量是異構(gòu)的，且不能補(bǔ)充。

2.2 相關(guān)定義

定義1:輪是從所有傳感器節(jié)點(diǎn)收集一次數(shù)據(jù)，并傳送到Sink節(jié)點(diǎn)的過程。

定義2:在一輪中節(jié)點(diǎn)vi在樹T上的能量耗費(fèi)S(T，vi)為:

式中，C(T，vi)為節(jié)點(diǎn)vi在樹T上孩子的數(shù)量;D(T，vi)=C(T，vi)+1為節(jié)點(diǎn)vi在樹T上的度數(shù)。

定義3:節(jié)點(diǎn)的生命周期是節(jié)點(diǎn)vi在一棵樹T中能存活的輪數(shù)。存活指節(jié)點(diǎn)vi的能量E(vi)＞0。節(jié)點(diǎn)vi在一棵樹T中的生命周期可定義為:

定義4:樹的生命周期是樹T中第一個(gè)節(jié)點(diǎn)死亡時(shí)，該節(jié)點(diǎn)存活的輪數(shù)。定義為:

定義5:最優(yōu)樹是根據(jù)當(dāng)前網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量水平構(gòu)造的一棵生成樹，其生命周期比網(wǎng)絡(luò)中其他生成樹的生命周期都要大。定義為:

式中，T'為網(wǎng)絡(luò)G中任意一棵生成樹;TS(G)為圖G中所有生成樹的集合。

定義6:瓶頸節(jié)點(diǎn)是指一棵樹中最早消耗完能量的節(jié)點(diǎn)，其生命周期與樹的生命周期一致。

2.3 問題描述

在一些持續(xù)性的監(jiān)視應(yīng)用中，傳感器網(wǎng)絡(luò)的延遲與樹的高度是密切相關(guān)的。此外，網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量n等于樹上各層節(jié)點(diǎn)孩子的總和，即

式中，h'為樹高;hi為樹上第i層所有節(jié)點(diǎn)的集合。根據(jù)式(3)，如果n是固定的，則樹中每個(gè)節(jié)點(diǎn)的度越小，樹的高度越大;反之，樹高越小。因此，要得到越小的延遲，需要越小的樹高，但是這樣樹上節(jié)點(diǎn)的度會(huì)比較大。

另一方面，根據(jù)式(1)和式(2)，生命周期最大的樹可以表示為:

由于Erx和Etx是固定的，只有D(T，vi)可以調(diào)節(jié)，是主要的優(yōu)化目標(biāo)。為了簡(jiǎn)化表達(dá)，對(duì)式(4)進(jìn)行等價(jià)變換:

式中，c=Etx/Erx－1。根據(jù)式(5)，要使樹的生命周期最大，每個(gè)節(jié)點(diǎn)的度越小越好。但是根據(jù)式(3)這樣會(huì)增加樹的高度，加大時(shí)間延遲，與最小延遲的要求矛盾。因此，樹的生命周期最大和最小時(shí)間延遲這兩個(gè)目標(biāo)是相互矛盾的，很難同時(shí)實(shí)現(xiàn)。因此，研究的問題是:在限定延遲的條件下，如何使得樹的生命周期最大。

3 算法DBDG的設(shè)計(jì)

首先，利用網(wǎng)絡(luò)G的拓?fù)錁?gòu)造一棵最少跳生成樹T。方法為:先將圖G中所有的邊賦予相同的權(quán)值1，然后采用Dijkstra算法從Sink節(jié)點(diǎn)出發(fā)求解到各個(gè)節(jié)點(diǎn)的最短路徑即可。樹T肯定是網(wǎng)絡(luò)G的所有生成樹中最矮的，但是樹上節(jié)點(diǎn)的度比較大。

接下來，以樹T為基礎(chǔ)進(jìn)行優(yōu)化，不斷地將樹上“瓶頸節(jié)點(diǎn)”的孩子轉(zhuǎn)移到“非瓶頸節(jié)點(diǎn)”上去，以減小“瓶頸節(jié)點(diǎn)”的度(D(T，vi))。但是，D(T，vi)在式(5)中是式子的分母，并不容易進(jìn)行調(diào)整。因此，將式(5)轉(zhuǎn)換為如下等價(jià)的形式:

定義

稱為樹T的最大反生命周期，r(T，vi)是樹T上節(jié)點(diǎn)vi的反生命周期。這樣，問題max Ltree(T)就轉(zhuǎn)化為求樹的最大反生命周期最小化問題，即

此外，要減少“瓶頸節(jié)點(diǎn)”的度，首先要明確哪些節(jié)點(diǎn)屬于“瓶頸節(jié)點(diǎn)”。根據(jù)定義6，“瓶頸節(jié)點(diǎn)”是與樹T的生命周期(或反生命周期)一致的節(jié)點(diǎn)。再觀察式(6)，除去Sink節(jié)點(diǎn)，樹T上節(jié)點(diǎn)反生命周期的最小變化幅度是δ=1/Emax，其中因此，根據(jù)反生命周期大小將樹上節(jié)點(diǎn)劃分到3個(gè)不同的集合V1、V2、和V3中:

① V1={vi|r(T)－δ＜r(T，vi)≤ r(T)，vi∈V}，在這個(gè)集合中節(jié)點(diǎn)的反生命周期與樹T的反生命周期在同一區(qū)間內(nèi)，屬于“瓶頸節(jié)點(diǎn)”。

② V2={vi|r(T)－δ－1/E(vi)＜r(T，vi)≤r(T)－δ，vi∈V}，在這個(gè)集合中節(jié)點(diǎn)的反生命周期非常接近于“瓶頸節(jié)點(diǎn)”的反生命周期。如果它們的孩子增加一個(gè)，它們就會(huì)變?yōu)椤捌款i節(jié)點(diǎn)”。因此，稱這個(gè)集合中的節(jié)點(diǎn)為“次瓶頸節(jié)點(diǎn)”。

③ V3=V－V1－V2，這個(gè)集合中節(jié)點(diǎn)的負(fù)載較輕，即使增加一個(gè)孩子也不會(huì)成為“瓶頸節(jié)點(diǎn)”，稱為“富裕節(jié)點(diǎn)”。

接著，再定義算法DBDG中“優(yōu)化”操作的含義為:在樹T中針對(duì)某個(gè)節(jié)點(diǎn)x的優(yōu)化，就是從圖G中選擇一條合適的邊(u，v)加入樹T并產(chǎn)生一個(gè)包含節(jié)點(diǎn)x的圈，接著再選擇性地刪除另一條在圈上且與x相連的邊，使x的度減1同時(shí)產(chǎn)生的新樹的高度不增長(zhǎng)或者增長(zhǎng)最小以不超過樹高限定h。

由于節(jié)點(diǎn)能量的異構(gòu)性，樹中任何一個(gè)節(jié)點(diǎn)都可能屬于“瓶頸節(jié)點(diǎn)”、“次瓶頸節(jié)點(diǎn)”或“富裕節(jié)點(diǎn)”中的一種。DBDG的主要目標(biāo)是優(yōu)化“瓶頸節(jié)點(diǎn)”，如果加入樹的邊(u，v)所依附的節(jié)點(diǎn)u和v都屬于“富裕節(jié)點(diǎn)”，則優(yōu)化操作可直接進(jìn)行;如果加入樹的邊(u，v)所依附的節(jié)點(diǎn)u和v有1個(gè)或2個(gè)都屬于“次瓶頸節(jié)點(diǎn)”，則優(yōu)化操作不能執(zhí)行。

綜上所述，算法DBDG的描述如下:

輸入:圖G和樹高限定h

輸出:高度最多為h的最大化生命周期樹

1.將圖G中的邊賦權(quán)值1，采用 dijkstra算法從v0出發(fā)構(gòu)造一棵最小跳生成樹T;

2.if(樹T的高度 ＞ h)return false;

3.Ischanged=TRUE;

4.while(Ischanged)

5.{Ischanged=FALSE;LV1= Φ ;i=0;

6. FindEdge(T，LV1);

7. while(i＜Length(LV1))

8. {訪問記錄LV1［i］，將其包含的邊(u，v)加入樹 T中產(chǎn)生一個(gè)圈C;

9. for(圈C中的每一個(gè)“瓶頸節(jié)點(diǎn)”vj)

10. if(Optimal(vj，T)){Ischanged=TRUE;break;}

11. if(Ischanged)break;∥成功優(yōu)化，進(jìn)入下一輪迭代

12. 把邊(u，v)從樹T中刪除;

13. i=i+1;

14. }∥while

15.}∥while

函數(shù)FindeEdge(T，＆LV1)的作用描述如下:

1.計(jì)算樹T及其上所有節(jié)點(diǎn)的反生命周期，判斷節(jié)點(diǎn)屬于V1、V2或V3中的哪個(gè)集合;

2.T0←T;

3.將樹T0中所有屬于V1和V2的節(jié)點(diǎn)刪除，得到一個(gè)組件的集合F;

4.for(圖G中每一條連接不同組件的邊(u，v))

5.{w(u，v)=level(T，u)+level(T，v);

6.根據(jù)權(quán)值 w(u，v)的大小，按遞增的次序?qū)⒂涗?u，v，w(u，v))保存到表LV1中;

7.}

4 實(shí)驗(yàn)結(jié)果與分析

假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)隨機(jī)地分布在一個(gè)200 m×200 m的正方形區(qū)域。每個(gè)節(jié)點(diǎn)的初始能量在［1J，1.5J］之間隨機(jī)分布，節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生率為1 000 bits/round，Erx=50 nJ/bit，所有節(jié)點(diǎn)的最大通信半徑為20 m。由于提出的數(shù)據(jù)收集方案是基于樹結(jié)構(gòu)的，因此選擇基于樹的算法FHT、IAA、DBMDST來進(jìn)行對(duì)比。采用Matlab進(jìn)行模擬實(shí)驗(yàn)。設(shè)定了2個(gè)實(shí)驗(yàn)場(chǎng)景:場(chǎng)景1中Sink節(jié)點(diǎn)位于區(qū)域的中心，坐標(biāo)(50，50);場(chǎng)景2中Sink節(jié)點(diǎn)位于區(qū)域的邊緣，坐標(biāo)(100，50)。在2個(gè)場(chǎng)景中以50為增量，分批放置100～400個(gè)節(jié)點(diǎn)。分別觀察各個(gè)算法的生命周期和生成樹的樹高，實(shí)驗(yàn)的結(jié)果是各個(gè)算法執(zhí)行100次后的平均結(jié)果，如圖1、圖2、圖3和圖4所示。

圖1 場(chǎng)景1中的生命周期對(duì)比

圖2 場(chǎng)景1中的樹高對(duì)比

圖3 場(chǎng)景2中的生命周期對(duì)比

圖4 場(chǎng)景2中的樹高對(duì)比

由圖1和圖2可以看到在場(chǎng)景1中，不同的節(jié)點(diǎn)密度下，最少跳樹FHT的生命周期最小，這是因?yàn)樗m然樹高最小但樹上節(jié)點(diǎn)的度很大，而且不能均衡節(jié)點(diǎn)的能量消耗。IAA樹的生命周期最大，這是因?yàn)樗鼪]有高度限制，算法能對(duì)樹上節(jié)點(diǎn)進(jìn)行近似最優(yōu)的優(yōu)化。但是，IAA的樹高明顯比FHT的樹高大很多。DB-MDST在與FHT同樣樹高的限制下，由于只對(duì)度最大的節(jié)點(diǎn)進(jìn)行了部分優(yōu)化，沒有實(shí)現(xiàn)負(fù)載均衡，因此樹生命周期比 FHT高，但是比DBDG低。

在圖3和圖4所示的場(chǎng)景2中，與場(chǎng)景1相比，F(xiàn)HT的平均生命周期增加了18%，IAA的平均樹生命周期基本保持不變，DB-MDST的平均樹生命周期增加了3%，DBDG的平均樹生命周期增長(zhǎng)了24%。這是由于Sink節(jié)點(diǎn)位于區(qū)域的邊緣，使得位于區(qū)域另一端的節(jié)點(diǎn)到它的距離更遠(yuǎn)，需要更多跳才能到達(dá)。因此，F(xiàn)HT樹的高度增加了(在場(chǎng)景1中是最大是6，在場(chǎng)景2中最大是9)。雖然FHT的樹高增加了，減輕了對(duì)DB-MDST樹高的限制，但DB-MDST的樹生命周期并沒有明顯提高。與DB-MDST不同，F(xiàn)HT樹高的增加和節(jié)點(diǎn)度的減少，都有利于DBDG進(jìn)行優(yōu)化操作，使其生成樹的生命周期有較大提高。因此，DBDG在低節(jié)點(diǎn)密度(100個(gè)和150個(gè))時(shí)做到了與IAA相同的優(yōu)化程度。只在節(jié)點(diǎn)密度增加后，其樹的生命周期才逐漸下降。綜上所述，DBDG在各種條件下均優(yōu)于DB-MDST和FHT。

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

無線傳感器網(wǎng)絡(luò)在工作過程中，節(jié)點(diǎn)會(huì)不斷地感知到周邊環(huán)境的數(shù)據(jù)。而在無線傳感器網(wǎng)絡(luò)任何一個(gè)應(yīng)用中，用戶都需要獲取相應(yīng)的數(shù)據(jù)進(jìn)行處理。采集網(wǎng)絡(luò)中用戶需要的數(shù)據(jù)，就被稱為數(shù)據(jù)收集。數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)中最重要的操作之一，能否有效地采集到合適的數(shù)據(jù)，直接關(guān)系到應(yīng)用的效果。針對(duì)目前的數(shù)據(jù)收集方法造成的能量浪費(fèi)和網(wǎng)絡(luò)傳輸延遲較大的問題，提出了一種限定延遲的算法DBDG，并通過仿真實(shí)驗(yàn)驗(yàn)證了本文方法的有效性。下一步工作主要研究密集部署網(wǎng)絡(luò)中的生命周期最大化問題。

［1］李方敏，徐文君，劉新華.無線傳感器網(wǎng)絡(luò)功率控制技術(shù)［J］.軟件學(xué)報(bào)，2008，19(3):716 －732.

［2］GAO Yan，HOU Jennifer，NGUYEN Hoang.Topology Control for Maintaining Network Connectivity and Maximizing Network Capacity under the Physical Model［C］∥Proc.of the IEEE 27th Conference on Computer Communications(INFOCOM2008)，2008:1 013 －1 021.

［3］AMMARI H M，DAS A K.A Trade-off between Energy and Delay in Data Dissemination for Wireless Sensor Networks Using Transmission Range Slicing［J］.Computer Communications，2008，31(9):1 687 －1 704.

［4］KIM Joohwan，LIN Xiaojun，SHROFF N B，et al.On Maximizing the Lifetime of Delay-sensitive Wireless Sensor Networks with Anycast［C］∥Proc.Of The IEEE 27th Conference on Computer Communications(INFOCOM2008)，2008:807－815.

［5］COHEN R，KAPCHITS B.An Optimal Algorithm for Minimizing Energy Consumption while Limiting Maximum Delay in a Mesh Sensor Network［C］∥Proc.of the IEEE 26 th Conference on Computer Communications(INFOCOM2007)，2007:258－266.

［6］WU Yan，F(xiàn)AHMY S，SHROFF N B.On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks:NP-Completeness and Approximation Algorithm［C］∥Proc.Of The IEEE 27th Conference on Computer Communications(INFOCOM2008)，2008:356 －360.

［7］KWON Soonmok，KIM Jeong-gyu，KIM Cheeha.An Efficient Tree Structure for Delay Sensitive Data Gathering in Wireless Sensor Networks［C］∥Pro of 22nd IEEE International Conference on Advanced Information Networking and Applications，2008:738 －743.

［8］CORMEN T，LEISERSON C，RIVEST R，et al.Introduction to algorithms［M］.McGraw-Hill，2001.