無線傳感器網(wǎng)絡中定位誤差對覆蓋控制算法的性能影響

(天津大學 計算機科學與技術學院， 天津 300072 )

摘 要：覆蓋控制是無線傳感器網(wǎng)絡中的一個基本問題，其主要目的是在保證全覆蓋要求的同時調(diào)度冗余節(jié)點輪流工作。為了找出冗余節(jié)點，當前的研究工作大都假定節(jié)點已經(jīng)擁有精確的地理位置信息，但實際應用中節(jié)點是無法獲取到精確的位置信息，為此，研究當節(jié)點位置信息存在誤差時對覆蓋控制算法的影響，分析了全覆蓋控制算法的缺陷和失效的原因，并通過仿真研究了多種因素變化時的網(wǎng)絡覆蓋率變化規(guī)律。結(jié)果表明，在節(jié)點位置存在誤差的情況下，網(wǎng)絡覆蓋率會隨著誤差率、網(wǎng)絡區(qū)域、節(jié)點密度和感知半徑的增加而降低。該結(jié)果為研究實用化的網(wǎng)絡覆蓋控制算法提供依據(jù)。

關鍵詞：無線傳感器網(wǎng)絡；定位誤差；覆蓋控制；地理位置信息

中圖分類號：TP393.02文獻標志碼：A

文章編號：1001-3695(2009)04-1460-03

Effect of location error on performance of coverage control in wireless sensor networks

SHI Gao-tao，WANG Ying-jin

(School of Computer Science Technology， Tianjin University， Tianjin 300072， China)

Abstract:Coverage control is the basic problem in wireless sensor networks. Its main objective is to schedule the redundancy node to work alternately under the requirement that the full-coverage is guaranteed. However， the existing works required accurate knowledge of the sensors locations to find the redundancy nodes， which could not be easily obtained.Studied the effect of location error on the performance of coverage control.Analyzed the shortcoming and the failure reason of the existing algorithms.Conducted some extensive simulations to evaluate the performance varying with different factor. The results show that the coverage rate will decrease with the increasing of error， network size， node density and sensing range.

Key words:sensor networks;location error;coverage control;geography information

0 引言

近年來，隨著微機電系統(tǒng)(micro-electro-mechanism system，MEMS)、無線通信、信息網(wǎng)絡與集成電路等技術的迅速發(fā)展，新興的無線傳感器網(wǎng)絡(wireless sensor networks，WSN)應運而生[1]。無線傳感器網(wǎng)絡一般需要大規(guī)模部署在目標區(qū)域中，與自然界緊密結(jié)合，對目標事件信息進行監(jiān)測。因此，覆蓋控制作為無線傳感器網(wǎng)絡中的一個基本問題，反映了網(wǎng)絡所能提供的感知服務質(zhì)量，可以使無線傳感器網(wǎng)絡的空間資源得到優(yōu)化分配，進而更好地完成環(huán)境感知、信息獲取和有效傳輸?shù)莫┤蝿铡＊?/p>

在當前無線傳感器網(wǎng)絡覆蓋控制算法中，根據(jù)應用的需求不同所提供的覆蓋能力也不盡相同。在一些苛刻的情況下，應用要求傳感器網(wǎng)絡能夠提供全覆蓋的網(wǎng)絡，也就是對目標區(qū)域的每個物理位置都至少被一個節(jié)點所覆蓋。因此，在網(wǎng)絡部署過程中大都是采用密集部署。然而，由于WSN中傳感器節(jié)點自身體積較小、電池能量資源有限，如何保證大規(guī)模網(wǎng)絡環(huán)境下傳感器節(jié)點能量的有效使用就成為需要關注的一項重要研究內(nèi)容，它直接影響到整個網(wǎng)絡生存時間能否充分延長[2]。典型的做法是采用輪換活躍和休眠節(jié)點的節(jié)能覆蓋方案，在保證網(wǎng)絡全覆蓋要求的條件下，最大化輪換節(jié)點集合數(shù)目。

為了能夠準確找出輪換節(jié)點，一般的算法都借助于節(jié)點的地理位置信息進行判斷。節(jié)點的位置信息一般可以借助GPS或者分布式的定位協(xié)議來獲得。節(jié)點的地理位置信息使無線傳感器網(wǎng)絡的工作變得更加容易，但是，目前的多數(shù)研究都假設節(jié)點已經(jīng)通過某種方式獲取了節(jié)點的精確位置信息。這一假設過于理想化，導致提出的解決方法并不能得到實用。實際中，理論上并不存在完全精確的定位系統(tǒng)和協(xié)議，也就是說任何一種定位技術總是存在著誤差。在這種情況下，對于過于依賴精確地理位置的算法和協(xié)議，就可能無法正常工作。因此，基于這種假設的相關算法和協(xié)議無法在實際系統(tǒng)中得到應用。

直觀上來看，當節(jié)點的位置不精確時網(wǎng)絡覆蓋要求必然受到影響，但是對于這種影響的規(guī)律變化情況目前尚不清楚。盡管定位的誤差不容忽視，但是當前對此的研究工作卻很少，特別是對于基于節(jié)點地理信息的覆蓋控制算法的性能研究尚未見有報道。已有的工作大都集中在定位誤差對geo-routing的影響上[3，4]。為此，本文對網(wǎng)絡覆蓋控制算法存在定位誤差時的性能影響進行分析和研究，并通過仿真的方法考察一個典型的覆蓋控制算法的性能變化情況進行，找出存在定位誤差的情況下該覆蓋控制算法性能變化規(guī)律，為設計更加實用的覆蓋控制算法提供依據(jù)。

1 相關工作

無線傳感器網(wǎng)絡中的定位誤差已引起研究人員的關注。文獻［5］對誤差的來源、模型和誤差對最小路徑暴露、最短路徑等問題的影響進行了研究。作者認為，定位誤差產(chǎn)生的主要原因不是單方面的，而是由測量技術、有限的精度、目標函數(shù)相關、難處理的優(yōu)化任務和定位算法等多方面決定的。

根據(jù)文獻[6]，定位也會產(chǎn)生不一致性問題，主要有以下幾種類別：絕對定位不精確、相對距離不精確和絕對定位不一致。其中，絕對定位不精確最為普遍，其思想是每個節(jié)點的實際位置和自身能獲得到的位置之間存在偏差。由于節(jié)點進行覆蓋控制算法時通過鄰居之間交換位置關系進行，本文的研究將基于這種誤差模型。

文獻[7]對無線傳感器網(wǎng)絡中的定位誤差的特點進行了研究，分析總結(jié)了誤差源，研究了定位誤差的Cramer-Rao界，給出了如何提高精度的建議。文獻[8]使用貝葉斯方法分析了定位誤差的下界進行了研究，詳細分析了三種定位技術的誤差特點。

當前的研究工作主要圍繞著誤差模型及對geo-routing的影響進行研究，對于覆蓋控制算法的影響尚未見報道。

2 全覆蓋及定位誤差的影響分析

2.1 覆蓋控制算法的基本思想

在無線傳感器網(wǎng)絡中，節(jié)點主要是感知周圍環(huán)境信息，因此，一般情況下，它都具有一個覆蓋區(qū)域。由于網(wǎng)絡的密集部署，每個節(jié)點的覆蓋區(qū)域都可能與其鄰居節(jié)點相互重疊，常常存在一個節(jié)點的覆蓋區(qū)域被其鄰居節(jié)點完全覆蓋，造成節(jié)點覆蓋區(qū)域的冗余。這種覆蓋冗余除了會帶來信息采集的冗余，還增加了通信沖突發(fā)生的可能性。圖1(a)給出一個冗余節(jié)點的例子。其中節(jié)點S的覆蓋范圍被其周圍鄰居節(jié)點所瓜分。因此，如果將這些冗余節(jié)點關閉，使之與其他節(jié)點輪流工作將會延長網(wǎng)絡壽命，降低數(shù)據(jù)冗余，提高網(wǎng)絡性能。可見，這種通過覆蓋控制的節(jié)能算法基本思想是在保證網(wǎng)絡全覆蓋的情況下關閉盡可能多的工作節(jié)點，并使它們輪流工作，從而延長網(wǎng)絡的壽命。

使用覆蓋控制策略達到節(jié)能目的需要考慮兩個問題，即網(wǎng)絡覆蓋質(zhì)量與網(wǎng)絡的連通性。為了判斷節(jié)點是否冗余，一個最簡單的方法就是借助節(jié)點的幾何位置關系。文獻[9]提出了一個根據(jù)節(jié)點幾何位置判斷網(wǎng)絡是否是k覆蓋的算法，保證每個物理點都至少被k個傳感器節(jié)點覆蓋。Tian等人[10]提出了一個覆蓋控制算法，每個節(jié)點判斷鄰居是否可以管理該節(jié)點的覆蓋范圍，進而決定是否睡眠。Zhang[11]和Wang[12]獨立證明了網(wǎng)絡連通和覆蓋關系的充分必要條件，并研究如何使用最少的節(jié)點數(shù)達到全覆蓋。Jiang[13]使用Voronoi圖的方法來選擇最小數(shù)目的工作節(jié)點集創(chuàng)建全覆蓋的網(wǎng)絡。

以上方法的區(qū)別在于判斷節(jié)點冗余的方法，大都借助于節(jié)點的精確地理信息，因此，有必要進行研究當節(jié)點的位置存在誤差時這些算法的性能變化情況。

2.2 定位誤差對覆蓋控制算法的影響分析

本節(jié)將從兩個方面考察全覆蓋控制算法的性能。

1)基于節(jié)點地理信息的全覆蓋策略缺陷

2.1節(jié)中給出的基于節(jié)點幾何位置的算法都期望能夠獲得全覆蓋的網(wǎng)絡，即整個網(wǎng)絡區(qū)域中每個點至少被k個節(jié)點覆蓋。然而，仔細分析圖1(b)能夠研究發(fā)現(xiàn)，這種策略事實上不利于網(wǎng)絡的覆蓋。在圖中，位于邊界的節(jié)點將整個網(wǎng)絡區(qū)域劃分成兩部分，分別是邊長為L的正方形區(qū)域和寬為r的帶狀環(huán)形區(qū)域。根據(jù)全覆蓋的要求，邊界節(jié)點需要時刻處于工作狀態(tài)來保證目標區(qū)域被完全覆蓋，從而沒有機會休眠，這樣當節(jié)點工作一段時間之后就會因能量耗盡而失效，從而導致覆蓋區(qū)域面積逐漸縮小。

為了驗證這一分析，圖2是在200×200的區(qū)域內(nèi)隨機撒放200個節(jié)點運行文獻[9]提出的覆蓋控制算法時網(wǎng)絡中節(jié)點狀態(tài)變化圖。從左到右分別是算法運行0，20，40，80輪時抓拍的圖片。其中，實心節(jié)點表示存活節(jié)點；空心節(jié)點表示能源耗盡的死亡節(jié)點。從中可以看到，整個網(wǎng)絡出現(xiàn)了類似于剝洋蔥的現(xiàn)象，節(jié)點從外部邊緣到內(nèi)部逐漸死亡，從而導致覆蓋面積逐漸縮小。一個顯著的現(xiàn)象是位于最外緣的節(jié)點在第20輪之后全部死亡。造成這種現(xiàn)象的主要原因是位于邊界的節(jié)點根據(jù)全覆蓋算法的思想沒有機會得到休眠，只能一直處于工作狀態(tài)。稱該現(xiàn)象為邊界效應。這種情況在一些應用中是不可接受的，如關鍵區(qū)域邊界檢測、森林防火等應用。

2)存在誤差時覆蓋控制算法的失效原因

當前在關閉冗余節(jié)點的相關算法中，大都假設節(jié)點具有精確的地理位置，這一假設過于理想化。當節(jié)點的位置并不精確時，算法就可能會失效。如圖3所示，假設A、B、C、D、E節(jié)點是按照某種協(xié)議測量得到的位置，其覆蓋區(qū)域用實線圓表示，節(jié)點A′、B′、C′、D′、E′等節(jié)點分別是A、B、C、D、E的實際位置，其覆蓋區(qū)域用虛線圓表示。當前控制覆蓋算法都假定節(jié)點自身了解的幾何位置是精確的，那么根據(jù)這一假定，算法會判斷出節(jié)點A的覆蓋區(qū)域被其周圍鄰居節(jié)點完全覆蓋，按照覆蓋控制算法的思想，節(jié)點A應當睡眠。然而，由于節(jié)點的實際位置并不能精確得到，那么當節(jié)點A睡眠之后整個覆蓋區(qū)域如圖3(a)所示，節(jié)點A所覆蓋的區(qū)域存在一塊沒有被其他節(jié)點覆蓋，從而導致算法失效。

3 仿真驗證

盡管定位誤差降低了網(wǎng)絡覆蓋率這一現(xiàn)象是很直觀的，但是覆蓋率的變化規(guī)律卻不容易發(fā)現(xiàn)。為了更加清晰地發(fā)現(xiàn)定位誤差對基于節(jié)點地理位置的覆蓋控制算法的影響，本節(jié)使用仿真的方法從不同的角度考察文獻[9]提出的算法性能變化情況。

假設網(wǎng)絡原始覆蓋面積為C，算法執(zhí)行后的覆蓋面積為C′，那么覆蓋率可以定義為C′/C。由于無法精確得到覆蓋面積，筆者采用近似的方法進行統(tǒng)計，將整個網(wǎng)絡覆蓋區(qū)域劃分成1×1的網(wǎng)格，通過統(tǒng)計網(wǎng)格個數(shù)來計算網(wǎng)絡的覆蓋面積。

在定位協(xié)議中，一般誤差值和節(jié)點的通信半徑密切相關。為了考察方便，本文將誤差率定義為

誤差率=(x-x′)2+(y-y′)2/r

其中：(x，y)是指節(jié)點的精確坐標；(x′，y′)是指節(jié)點通過定位協(xié)議獲得的坐標；r是節(jié)點的感知半徑。

圖4給出了四種不同的感知半徑情況下算法覆蓋率隨定位誤差的變化情況。其中每個數(shù)據(jù)點都是10次結(jié)果的平均值。網(wǎng)絡區(qū)域大小是300×300個單位，可以看出，隨著定位誤差的逐漸增大，覆蓋率也會逐漸下降。此外，當感知半徑不同時，如果定位誤差相同，真正得到的誤差距離是不同的，為了考察在相同的定位距離下性能變化的情況，剩余的仿真固定感知半徑不變。

圖5給出了在節(jié)點感知半徑保持不變的情況下不同節(jié)點個數(shù)隨誤差率變化、覆蓋率變化的情況。可以看出，網(wǎng)絡的節(jié)點密度也會對性能變化產(chǎn)生影響，當網(wǎng)絡節(jié)點密度增大時，網(wǎng)絡的覆蓋率相應降低。為此筆者考察了節(jié)點個數(shù)保持不變，在網(wǎng)絡區(qū)域大小變化的情況下覆蓋率的變化情況。圖6給出了該種情況下的覆蓋率變化情況，可以看出，這一趨勢和圖5基本一致。這說明覆蓋率的變化會隨著網(wǎng)絡密度、感知半徑和誤差度等因素的影響。

4 結(jié)束語

本文對無線傳感器網(wǎng)絡中的覆蓋控制算法存在定位誤差情況下的性能進行了研究，發(fā)現(xiàn)基于節(jié)點地理信息的覆蓋控制算法不僅不利于網(wǎng)絡的全覆蓋，而且在存在誤差時算法無法到達預定的要求，網(wǎng)絡覆蓋率會隨著節(jié)點定位誤差程度、感知半徑和網(wǎng)絡密度等因素的影響。這一現(xiàn)象表明，依賴于節(jié)點精確位置的覆蓋控制算法在實際應用中將無法提供期望的性能，存在著定位誤差的條件下，這類算法無法正常工作。因此，如果忽略了定位誤差，那么這類算法在實際的應用中將會產(chǎn)生錯誤的結(jié)果。本文的研究將為提出更加實用化的覆蓋控制算法提供依據(jù)。未來的工作是在此基礎上研究實用化的全覆蓋控制算法。

參考文獻：

［1］

AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4):393-422.

[2]REN Yan，ZHANG Si-dong，ZHANG Hong-ke.Theories and algorithms of coverage control for wireless sensor networks[J].Journal of Software，2006，17(3):422-433.

[3]SEADA K，HELMY A，GOVINDAN R.On the effect of location errors on geographic face routing in sensor networks[C]//Proc of the 3rd International Symposium in Information Processing in Sensor Networks.Berkely，CA:[s.n.]，2004.

[4]KIM Y，LEE J J，HELMY A.Impact of location inconsistencies on geographic routing in wireless networks[C]//Proc of the 6th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems.San Diego:[s.n.]，2003.

［5］SLIJEPCEVIC S，MEGERIAN S，POTKONJAK M.Location errors in wireless embedded sensor networks: sources， models， and effects on applications[J].ACM Mobile Computing and Communications Review，2002，6(3):67-78.

[6]WITT M，TURAU V.The impact of location errors on geographic routing in sensor networks[C]//Proc of the 2nd International Conference on Wireless and Mobile Communications.Bucharest，Romania:[s.n.]，2006.

[7]SAVVIDES A，GARBER W L，ADLAKHA S，et al.On the error characteristics of multihop node localization in Ad hoc sensor networks[C]//Proc of the 2nd International Conference on Information Processing in Sensor Networks.Palo Alto，California:[s.n.]，2003.

[8]WANG Han-biao，YIP L，YAO K，et al.Lower bounds of localization uncertainty in sensor networks[C]//Proc of IEEE International Conference on Acoustics， Speech， and Signal Processing.Montreal:[s.n.]，2004.

[9]HUANG Chi-fu，TSENG Y C.The coverage problem in a wireless sensor network[C]//SIVALINGAM K M，RAGHAVENDRA C S.Proc of the 2nd ACM International Workshop on Wireless Sensor Networks and Applications.New York:ACM Press，2003:115-121.

[10]TIAN Di，GEORGANAS N D.A node scheduling scheme for energy conservation in large wireless sensor networks[J].Wireless Communications and Mobile Computing，2003，3(2):271-290.

[11]ZHANG Hong-hai，HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad hoc Wireless Networks，2005，1(1):89-124.

[12]WANG Xiao-rui，XING Guo-liang，ZHANG Yuan-fang，et al.Integrated coverage and connectivity configuration in wireless sensor networks[C]//AKYILDIZ I F，ESTION D.Proc of ACM International Confe-rence on Embedded Networked Sensor Systems.New York:ACM Press，2003.