無線傳感器網絡定位系統的設計原則與方法研究

摘要:通過分析現有的無線傳感器網絡定位系統，總結出定位系統的設計原則;對存在于定位系統和算法中的各種影響因素進行詳細分析，指明各種因素影響定位的具體原因;在此基礎上提出了切實可行的解決方案，為定位系統的設計提供實驗依據#65377;

關鍵詞:定位系統;連通性;測距誤差;錨節點密度

中圖分類號:TP301文獻標志碼:A

文章編號:1001-3695(2007)10-0089-04

0引言

無線傳感器網絡(wireless sensor network，WSN)是下一代“無處不在的計算”的關鍵技術#65377;節點定位技術作為無線傳感器網絡的關鍵技術，引起了許多學者的興趣#65377;只有結合位置信息，傳感器獲取的數據才有實際意義#65377;目前根據傳感器節點的成本低#65380;能量消耗低和體積小的特點，研究出了很多滿足各種要求的節點定位算法[1];并根據不同的定位算法和應用環境實現了不同的定位系統#65377;

1992年ATT Laboratories Cambridge開發出了最早的室內定位系統Active Badge[2，3]#65377;它是偏重于緊密耦合型[4]和基于基礎設施[5]的定位系統#65377;隨后開發出了松散型定位系統，代表性的研究成果包括RADAR[6]#65380;Active bat[7]#65380;SpotON[8]#65380;Active office[9]等#65377;

2000年以后開始了對于松散耦合型和無須基礎設施的定位技術的關注和研究#65377;為了彌補緊密耦合定位系統的不足，MIT開發了最早的松散耦合型室內定位系統Cricket[10]#65377;美國RutgersUniversity的Dragos Niculescu利用距離矢量路由和GPS定位的思想于2001年和2003年提出了一系列分布式定位系統——合稱為APS (Ad hoc positioning system)[11~13]#65377;它共包括了六種定位算法，即DVhop[11]#65380;DVdistance[11，12]#65380;Euclidean[11，12]#65380;DVcoordinate[12]#65380;DVbearing和DVradial[13]#65377;Cameron WhiteHouse基于Ad hoc的無線傳感器網絡開發了Calamari[14]定位系統;它使用超聲波(TOF)和信號強度(RSS)測距技術#65377;此外，還開發出了在人工部署環境中利用GPS設備定位的系統，即移動GPS[15]定位系統#65377;它的定位精度很高，但其實現成本相對較高#65377;

以上這些定位系統在WSN定位領域具有一定的代表性，但每一種系統都有它的適用范圍和局限性#65377;開發定位系統時須考慮網絡的基礎設施#65380;網絡的連通性#65380;節點密度#65380;錨節點密度#65380;測距誤差#65380;通信開銷和計算開銷等影響定位的因數;定位系統還要有一定的容錯性和抗毀性，必須保證定位系統的可靠性#65377;因此，從定位算法理論研究到定位算法的實現并不是一蹴而就的，必須對節點定位算法從理論到實現過程中更多的細節進行研究#65377;本文將在已實現定位系統的基礎上，提出設計定位系統的一般性原則;并就從提高網絡的連通度#65380;增加網絡的覆蓋率#65380;降低錨節點密度#65380;減少測距誤差等各方面，提出一般性的解決方法#65377; 

1設計原則

雖然不同定位系統的整體設計方案是不一樣的，但它們還是有很多共同之處的#65377;本文著重闡述設計定位系統應該遵循的一般性原則[14]#65377;

1)可擴展部署

定位系統應該是可擴展的，也就是說計算#65380;能源#65380;帶寬和基礎設施的成本不隨網絡的變化而增加#65377;由于傳感器網絡能夠任意大，與網絡大小的增加速度相比，傳感器網絡定位系統基礎設施的部署時間的增加才會較慢#65377;這是實現大規模無線傳感器網絡定位的基礎#65377;

2)事件驅動

定位系統應該是基于事件驅動的#65377;由于傳感器節點經常是固定的，定位系統在少有的節點移動或新節點移入的情況下應該是活動的#65377;為了系統更有效，應該使用事件驅動，而不是使用超低的能源#65377;

3)簡單和近似的操作

定位系統應該具有簡便#65380;精度高的特點#65377;便宜#65380;簡單和近似的硬件設備與簡便的定位算法具有同樣重要的作用#65377;無論定位算法多么精確，任何傳感器網絡的定位系統都不能使用高能源消耗的硬件和詭辯的節點定位算法#65377;

4)容錯性和抗毀性

傳感器網絡由于自身節點能力不一致#65380;測距#65380;能耗等問題，導致網絡的不穩定，是WSN一個很突出的問題#65377;這就要求定位系統有一定的容錯能力和抗毀能力#65377;

2定位系統各種影響因數分析

影響定位系統的因素有很多，如網絡的連通性#65380;節點密度#65380;錨節點密度#65380;測距誤差#65380;基礎設施#65380;通信開銷和計算開銷等#65377;

2.1網絡的連通性與覆蓋率

目前，已經實現了基于連通度和跳數的定位系統，如APS#65377;此外，MIT開發的室內定位系統Cricket[10]和南加州大學的Nirupama Bulusu的質心算法[11]，也完全是基于網絡連通性的#65377;因此，網絡的連通度對于定位算法是一個很重要的影響因素#65377;

2.1.1相關概念

每個傳感器節點都有無線通信模塊#65377;在一定的發射功率下，節點最遠能發送的距離，即為節點的通信半徑#65377;網絡的連通性定義為如果節點之間可以直接互相通信，就稱這對節點是連通的#65377;覆蓋率是指網絡中能夠定位節點占全部節點的比率#65377;

如何保證一定區域內的傳感器節點在滿足連通可靠性要求情況下連接成一張網絡，即在節點的通信半徑一定的情況下，要在一定區域內拋撒多少點才能基本可靠地形成一張網#65377;形成網的連通概率為多少，定位系統達到的覆蓋率能有多大， 這是基于網絡連通度定位系統必須關心和解決的問題#65377;

2.1.2存在的問題

1)連通性圖1揭示了三個問題:定義連通性是不清晰的，因為有些節點之間既不能說是連通的，也不能說是不連通的，節點之間是以一定的概率連通的;不能定義射頻信號的連通性能夠將成對的節點區分成與給定的距離相比是近還是遠;很多成對的節點，它們的連通性接近連通的界限，很容易在實際距離之間靠近或靠遠地波動#65377;

2)跳數圖2表明了信息從基站節點(5，0)廣播兩跳的情形#65377;在這種情況下，一個簡單的泛洪之后，跳數用于指示距離是一個非常不可靠的方法;節點8和13具有同樣的跳數信息，但節點13到(5，0)點之間的距離卻是節點8到基站節點距離的3~4倍;在一些特別情況下，這個值將會更大#65377;這是設計使用基于跳數的定位系統時必須要考慮解決的問題#65377;

3)節點區別文獻[14]中的實驗表明，即使在一個非常理想的環境，對于一些特別的節點，能夠接收信號的最遠節點距離比接收不到信號的最近節點的距離遠400%#65377;這表明不同節點的發射能力#65380;接收能力也存在著很大的區別，這也是影響定位系統穩定性的一個很重要的原因#65377;

4)通信半徑和功耗因為無線傳輸的發送功耗和發送距離R的平方到四次方成反比[17]，所以網絡半徑的大小直接關系到網絡的功耗#65377;通信半徑大小直接關系到每個節點的功耗，節點的個數直接關系到網絡的成本#65377;如何在滿足組成網絡可靠性概率的前提下，合理地選擇節點數和通信半徑是關系網絡壽命和成本的關鍵#65377;

2.1.3解決方法

1)發射功率的設定與節點數量的選擇一般情況下，對于基于跳數的定位系統，為了提高定位精度，都不應將發射功率值設置得很大#65377;這在另一個方面也節省了網絡的功耗#65377;雖然在一定程度上增加了節點的數量，但在實驗中將看到這種犧牲是值得的，特別是對定位區域不大的情況#65377;例如，DVhop算法的實現，對于較小的定位區域，采用較小的發射功率值的定位效果明顯優于功率大的情況#65377;因為對于一個定位區域很小的情況，區域內的節點區分能力很強;否則，所有的節點將獲取同樣的跳數值，這意味著所有的未知節點獲取的定位坐標是一樣的，這樣的定位效果對于定位系統來說是無效的;而且，功率值小的還有一個好的效果，即定位精度會較高#65377;

利用建立的模型就可以在保證網絡連通可靠性的同時，選出合理的節點數#65377;

2)連通性#65380;跳數#65380;節點的復雜性連通性#65380;跳數#65380;節點這些因素表現出的復雜性是定位系統出現不穩定的一個很重要的原因#65377;這是考慮使用連通性#65380;跳數進行定位需要解決的一個很突出的問題#65377;僅僅從單方面解決這個問題是很困難的，必須考慮使用其他的定位技術進行輔助控制#65377;例如，測距技術，特別是RSSI測距技術#65377;因為它不需要任何額外的硬件支持;當定位算法估計出距離值之后，再與測距技術估計的距離值進行比較#65380;權衡，這可以有效抑制因跳數不規范等因素造成的誤差，使定位系統具有很好的穩定性#65377;

2.2錨節點密度

很多定位算法對錨節點密度的要求很高#65377;例如，DVHop算法#65380;凸規劃定位算法[19]需要10%的錨節點密度;DVcoordinate和Euclidean算法在大于20%錨節點密度下，才可穩定地保證網絡中80%以上的節點實現定位[1]#65377;

為了降低開始部署時的錨節點密度，可以考慮將已定位的未知節點升級為錨節點#65377;AHLos[20]算法利用將已定位的未知節點升級為錨節點來解決錨節點稀疏問題，但它存在一個問題，即容易造成累計誤差#65377;為了解決這個問題，generic localized algorithm[21]詳細指定了未知節點接受位置估算并升級為錨節點的條件，以減少誤差累計#65377;算法中未知節點升級為錨節點的條件是通過多次三邊測量產生的冗余信息，選擇位置更加一致的節點#65377;總體的設計原則是要充分利用算法中產生的冗余信息，這也是提高系統容錯和抗毀能力一種很好的方法#65377;

2.3測距誤差

測距技術是任何定位技術的核心，主要有三種測距技術:連通度或是基于跳數的測量方法#65380;RSS和TOF(聲波飛行時間)#65377;基于連通度和跳數的測距技術已經作了詳細介紹#65377;TOF技術對硬件的需求很高，在這里只研究RSS技術#65377;

2.3.1RSS——接收信號強度

信號強度在室內復雜的環境中，由于障礙物或反射，使得信號強度用于指示距離是不可靠的#65377;很多傳感器網絡應用適合在理想的環境中測試信號強度，如室外，但這并不意味著RSS不能被用來估計節點之間的距離#65377;RSS在定位應用中有很廣泛的應用#65377;例如，SpotON定位系統和AHLos算法都是使用RSS技術進行定位的#65377;

影響RSS的環境因素[17]有:

a)高度#65377;天線離地面距離的微小變化，都將對RSS的值#65380;噪聲#65380;衰減率和測距帶來很大的影響#65377;

b)植被#65377;即使像雜草之類的植被在高度上有微小的變化，它都會對RSSI值產生很大的影響#65377;

c)發射功率#65377;雖然增加發射功率能夠增加信號的發射距離，減少衰減率，但它同時卻增加了噪聲#65377;

d)包裝#65377;在有些實驗中，節點的形狀#65380;電池的大小和節點周圍圍欄對RSS也會有極大的影響#65377;

e)室內環境#65377;在一個很大#65380;沒有墻的房間里，即使發射功率非常低，實驗依然會出現不可辨別的模式#65377;例如，兩個節點之間的距離很遠，但卻能獲取很合理的信號強度的衰減率#65377;

2.3.2測距誤差

由式(1)根據圖3的數據計算出來的關系圖如圖4所示#65377;圖4中的曲線表明測距誤差隨著距離的增加而增加#65377;當距離值大于30 ft時，error值偏大#65377;這樣的值被認為是不合理的，也就是說，在當前發射功率下，發射的最遠距離應該是30 ft#65377;設計定位系統時，必須考慮對通信距離過大的節點進行控制#65377;通常，認為當接收的信號強度值小于-80 dBm[22]時，該信號可以舍去#65377;若定位系統需要更遠的發射距離值，可以增加RF模塊的發射功率#65377;但同時也增加了信號的噪聲#65377;

文獻[14]中用大量的數據說明了求信號強度的平均值能夠有效地減少噪聲對測距誤差的影響#65377;但是這種方法不能減少由于障礙物或反射等環境因素造成的測距誤差，需要更好#65380;更有效的方法抑制測距誤差#65377;這種方法就是校正#65377;

沒有校正，任何測距都是沒有意義的#65377;當無線電波以另外一個無線電波的兩倍功率發送時，將導致高達100%的測距誤差#65377;發送器的功率變化也會影響觀察到的RSSI值[14]#65377;現有的校正技術[14，17]有統一校正#65380;聯合校正#65380;自動校正等#65377;Calamari定位系統經過簡單的校正可以達到大約30%的測距誤差#65377;

圖3表明在一個比較理想的環境中，隨著距離的增加，信號強度將成對數地衰減#65377;本文感興趣的是使用這條曲線在每一距離處下的測距誤差#65377;這個誤差主要由信號強度中的噪聲和信號強度的衰減率(曲線的斜率)造成的#65377;假設斜率在一個很短的距離之內是一個常量，可以用式(2)計算它的大約值:

error(cm)≈noise(dB)/attenuation_rate(dB/cm)(2)

Cooperative ranging[23，24]算法中采用循環求精過程對初始定位結果進行求精，降低測距誤差影響;twophase positioning算法[25]中提出了在循環求精的基礎上加入權值的方法，進一步遏制測距誤差的影響#65377;Generic localized algorithm指定了未知節點接受位置估算并升級為錨節點的條件，用以減少累計誤差#65377;還可以利用連通度和覆蓋率有可能產生的冗余信息來降低測距誤差和累計誤差的影響#65377;

2.4其他影響因素

無線傳感器網絡的成本始終是制約定位系統設計的一個很現實的問題#65377;它的能耗也在另一個方面給WSN定位系統的設計提出了一個難題#65377;總體設計原則是使用簡單#65380;近似的算法和硬件設備#65377;文獻[26]中詳細分析了幾種分布式定位算法的通信開銷和計算開銷#65377;為了節省能耗，盡量使用事件驅動機制和簡便的算法#65377;

當然，這些原則不是針對特定的應用環境，特定的環境可以有特定的設計#65377;類似于早期的基于基礎設施的定位系統Active Badge，這種定位系統的成本代價將是很高的#65377;移動GPS技術定位精度很高，是一種適合于人工部署環境中的合理解決方案，但是成本也很高#65377;

2.5小結

眾多的影響因素使得設計定位系統是一件很復雜的事情，設計時不可能兼顧所有的方面#65377;通過輔助方法#65380;冗余信息#65380;校正技術#65380;循環求精等方法在解決問題的同時也增加了新的問題，是因為將為這些操作付出額外的計算開銷和通信開銷#65377;最終的原則是要綜合考慮各種影響因素，權衡定位精度和成本#65380;開銷之間的關系，設計出合理的定位系統#65377;

3結束語

本文已經對定位系統和算法的影響因素作了詳細的闡述，提出了一個合理的設計原則，為具體實現一個定位系統提出了很多可行的方法#65377;下一步的工作就是在現有的設計原則和方法的指導下，結合連通度#65380;跳數和RSS測距技術，應用各種改善影響因素的方法，特別是提出改善連通性和跳數的有效方法，選擇一個較好的定位算法，實現適合本文應用環境的一個定位系統#65377;

參考文獻:

[1]王福豹，史龍， 任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，2005，16(5):857-868.

[2]WANT R，HOPPER A，FALCAO V，et al.The active badge location system[J].ACM Transactions on Information Systems，1992，10(1):91102.

[3]HARTER A，HOPPER A.A distributed location system for the active office[J].IEEE Network，1994，8(1):6270.

[4]BULUSU N.Selfconfiguring localization systems[D]. Los Angeles:University of California，2002.

[5]CAPKUN S，HAMDI M，HUBAUX J P.GPSfree positioning in mobile Ad hoc networks[C]//Proc of the 34th Annual Hawaii International Conference on System Sciences.Maui，Hawaii:IEEE Computer Society， 2001:3481-3490.

[6]BAHL P，VENKATA N P.RADAR:an inbuilding RFbased user location and tracking system[C]//Proc of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Los Alamitos:IEEE CS Press，2000:775-584.

[7]HARTER A，HOPPER A，STEGGLES P，et al.The anatomy of a contextaware application[C]//Proc of Mobile Computing and Networking.Seattle:ACM Press， 1999:59-68.

[8]HIGHTOWER J，BORIELLO G，WANT R.SpotON:an indoor 3D location sensing technology based on RF signal strength，UW CSE 000202[R].Seattle:University of Washington， Department of Computer Science and Engineering，2000.

[9]HARTER A，JONES A，HOOPER A.A new location technique for the active office[J].IEEE Personal Communications，1997，4(5):42-47.

[10]PRIYANTHA N B，CHAKRABORTY A，BALAKRISHNAN H.The Cricket locationsupport system[C]//Proc of the 6th ACM International Conference on Mobile Computing and Networking (ACM MOBICOM).Boston:ACM Press， 2000:32-43.

[11]NICOLESCU D，NATH B.Ad hoc positioning systems (APS)[C]//Proc of IEEE Global Telecommunications Conference (IEEE GLOBECOM’01).San Antonio， TX:IEEE Communications Society， 2001:2926-2931.

[12]NICULESCU D，NATH B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems，2003，22(4):267-280.

[13]NICULESCU D，NATH B.Ad hoc positioning system (APS) using AoA[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.San Francisco:IEEE Computer and Communications Societies， 2003:17341743.

[14]WHITEHOUSE C. The design of Calamari: an Ad hoc localization system for sensor networks[D].Berkeley:University of California，2002.

[15]STOLERU R，HE T，STABJIVUC J A.Walking GPS:a pratical solution for localization in manually deployed wireless sensor networks[C]//Proc of the 29thAnnual IEEE International Conference on Local Computer Networks.Washington， DC:IEEE Computer Society，2004:480-489.

[16]GANESAN D，KRISHNAMACHARI B，WOO A，et al.Complex behavior at scale:an experimental study of lowpower wireless sensor networks， UCLA/CSDTR 02-0013[R].Los Angeles:University of California，2002.

[17]WHITEHOUSE K，KARLOF C，CULLER D.Radio signal strength localization without dense， predeployed anchor nodes[R].Berkeley:University of California，2004.

[18]孫永進，孫雨耕，房朝暉. 無線傳感器網絡的連通與覆蓋[J]. 天津大學學報，2005，38(1):1417.

[19]DOHERTY L，GHAOUI L E，KRISTOFER S J.Convex position estimation in wireless sensor networks[C]//Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies.Anchorage.AK:IEEE Computer and Communications Societies， 2001:16551663.

[20]SAVVIDES A，CHIHCHIEH H，SRIVASTAVA M B.Dynamic finegrained localization in Ad hoc networks of sensors[C]//Proc of Mobile Computing and Networking.Rome:ACM Press， 2001:166179.

[21]MEGUERDICHIAN S，SLIJEPCEVIC S，KARAYAN V，et al.Localized algorithms in wireless Ad hoc networks:location discovery and sensor exposure[C]//Proc of the ACM International Symposium on Mobile Ad hoc Networking Computing.Long Beach:ACM Press，2001:106116.

[22]TinyOS getting started guide[EB/OL]. http://www.qlimu.com/doc/TinyOS%20Getting%20Started%20Guide%207430002203_A.pdf.

[23]BEUTEL J.Geolocation in a PicoRadio environment[D].[S.l.]:ETH Zurich Electronics Laboratory，1999.

[24]SAVARESE C，RABAEY J M，BEUTEL J. Locationing in distributed Ad hoc wireless sensor network[C]//Proc of IEEE International Conference on Acoustics， Speech， and Signal.Salt Lake:IEEE Computer Society， 2001:2037-2040.

[25]SAVARESE C，RABAY J K.Langendoen robust positioning algorithms for distributed Ad hoc wireless sensor networks[C]//Proc of the USENIX Technical Annual Conference.Monterey，CA:USENIX Press， 2002:317-327.

[26]王建剛，王福豹，段渭軍，等. 無線傳感器網絡分布式節點定位算法研究[J].計算機應用，2005，25(11):2468-2471.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”