基于路由信息的傳感網(wǎng)絡(luò)定位算法

1、    基于路由信息的傳感網(wǎng)絡(luò)定位算法1.引言無線傳感器網(wǎng)絡(luò)是近年來一個熱點研究領(lǐng)域，其中傳感器網(wǎng)絡(luò)定位技術(shù)也越來越受到人們的關(guān)注，這是因為傳感器網(wǎng)絡(luò)的大量應(yīng)用都依賴于節(jié)點的位置信息，例如在戰(zhàn)場偵察、生態(tài)環(huán)境監(jiān)測、地震洪水火災(zāi)等現(xiàn)場的監(jiān)控等應(yīng)用中，都需要知道傳感器節(jié)點的位置信息，從而獲知信息來源的準確位置。現(xiàn)有無線傳感器網(wǎng)絡(luò)定位系統(tǒng)種類繁多，實現(xiàn)方法各異12。具有代表性的有采用超聲波測距的TDOA(TimeDifferenceofArrival)系統(tǒng)3，基于RSSI    1.引言    無線傳

2、感器網(wǎng)絡(luò)是近年來一個熱點研究領(lǐng)域，其中傳感器網(wǎng)絡(luò)定位技術(shù)也越來越受到人們的關(guān)注，這是因為傳感器網(wǎng)絡(luò)的大量應(yīng)用都依賴于節(jié)點的位置信息，例如在戰(zhàn)場偵察、生態(tài)環(huán)境監(jiān)測、地震洪水火災(zāi)等現(xiàn)場的監(jiān)控等應(yīng)用中，都需要知道傳感器節(jié)點的位置信息，從而獲知信息來源的準確位置。    現(xiàn)有無線傳感器網(wǎng)絡(luò)定位系統(tǒng)種類繁多，實現(xiàn)方法各異12。具有代表性的有采用超聲波測距的TDOA(TimeDifference of Arrival)系統(tǒng)3，基于RSSI (Receive Signal Strength Indicator)的技術(shù)4，基于網(wǎng)絡(luò)連通性的質(zhì)心定位算法5，基于多跳傳感器網(wǎng)絡(luò)節(jié)點間跳

3、數(shù)的DV-Hop算法6等?，F(xiàn)有算法大多存在額外的硬件開銷，或需要較多已知位置的參考節(jié)點，而且都有較大的通信開銷，帶來了傳感器節(jié)點額外的功耗，這樣就降低了全網(wǎng)的生存周期。因此，需要針對無線傳感器網(wǎng)絡(luò)的具體場景，設(shè)計低成本，低開銷，易實現(xiàn)的定位算法。    2.基于路由信息的定位算法    2.1研究場景定義    無線傳感器網(wǎng)絡(luò)的應(yīng)用場景各異，對定位的需求也各不相同。因此，在進行定位算法的設(shè)計前，必須選定應(yīng)用場景進行有針對性的設(shè)計。本文選用傳感器網(wǎng)絡(luò)中廣泛應(yīng)用的大范圍數(shù)據(jù)采集場景，例如土壤溫濕度監(jiān)測、森林火

4、險預(yù)警、智能大廈人員數(shù)據(jù)采集等，作為研究前提。    在這種場景下，數(shù)量眾多的傳感器節(jié)點分布在較大范圍的區(qū)域內(nèi)，節(jié)點需要通過多跳路由將數(shù)據(jù)返回到一個或多個網(wǎng)關(guān)節(jié)點。所有傳感器節(jié)點不裝配GPS、超聲收發(fā)器、有向天線等額外的定位和測距設(shè)備，節(jié)點射頻模塊只具備射頻信號強度檢測能力(RSSI)，甚至RSSI能力也不具備（即只有通信功能）。為了方便下面的研究，進一步對場景作如下簡化定義：    1.傳感器節(jié)點數(shù)目表示為n,網(wǎng)關(guān)節(jié)點數(shù)目表示為m；    2.n個傳感器節(jié)點在區(qū)域內(nèi)隨機均勻分布，自身位置為(xi,yi)

5、均未知，其中i= 1.n；    3.m個網(wǎng)關(guān)節(jié)點在區(qū)域內(nèi)以某種規(guī)律分布，自身位置(xi,yi)均已知，其中i= n+1.n+m；    4.傳感器節(jié)點均以一定且相同的周期采集數(shù)據(jù)，節(jié)點間相對靜止；    5.節(jié)點采用無線全向天線進行互通信，RSS測距的先驗概率分布滿足高斯分布；    2.2設(shè)計思路    而且因為數(shù)據(jù)采集任務(wù)對網(wǎng)絡(luò)的存活時間要求一般較高，所以降低傳感器節(jié)點的功耗，即降低傳感器節(jié)點的通信開銷就成為設(shè)計定位算法中重要的因素。而現(xiàn)有

6、定位算法存在的主要問題就是通信開銷大，其中有一個重要原因是現(xiàn)有的研究將定位過程與網(wǎng)絡(luò)路由和數(shù)據(jù)采集看作獨立的過程，而事實上這兩個過程存在大量通信的重復(fù)，這樣就帶來了額外的通信開銷。本文的研究就是將路由協(xié)議與定位算法結(jié)合來減少這部分開銷，基本思路是通過在數(shù)據(jù)包上附加網(wǎng)絡(luò)路由信息來獲得部分節(jié)點間的連接和距離關(guān)系，然后根據(jù)這些關(guān)系來進行傳感器節(jié)點定位，該算法命名為RBSL(RoutinginformationBased Sensor Localization)。    本文選用了傳感器網(wǎng)絡(luò)中常用的定向擴散路由協(xié)議7(DirectedDiffusion)作為研究的基礎(chǔ)。定

7、向擴散路由協(xié)議是一種以數(shù)據(jù)為中心的路由協(xié)議，網(wǎng)關(guān)節(jié)點向所有傳感器節(jié)點發(fā)送對任務(wù)描述的“興趣”(Interest)，“興趣”會逐漸在全網(wǎng)中擴散，最終達到所有匹配“興趣”的傳感器節(jié)點，與此同時也建立起了從網(wǎng)關(guān)節(jié)點到傳感器節(jié)點的“梯度”，傳感器節(jié)點會沿著梯度最大的方向?qū)?shù)據(jù)傳回網(wǎng)關(guān)節(jié)點。定向擴散的原理示意圖如下圖1所示：    對于全網(wǎng)數(shù)據(jù)采集的場景，網(wǎng)關(guān)節(jié)點發(fā)送的“興趣”是采集所有節(jié)點數(shù)據(jù)。在建立梯度之后，每個一個傳感器節(jié)點都有一個自己對網(wǎng)關(guān)節(jié)點的最大“梯度”方向，即下一跳傳輸?shù)哪康墓?jié)點編號(ID)。若每個傳感器節(jié)點在發(fā)送數(shù)據(jù)包末尾都附加自己的下一跳節(jié)點ID，則在每一

8、個網(wǎng)關(guān)節(jié)點就都可以獲得網(wǎng)絡(luò)中n條鏈路的連接情況，即獲得了到一個網(wǎng)關(guān)節(jié)點的樹狀路由表。將m個網(wǎng)關(guān)節(jié)點的數(shù)據(jù)進行綜合就可以獲得更多條鏈路的連接情況。將獲得的n個傳感器節(jié)點和m個網(wǎng)關(guān)節(jié)點之間的連接關(guān)系表示為對稱連接矩陣L(n+m,n+m)，其中Lij= 1 表示i, j節(jié)點存在路由鏈路，反之Lij = 0表示不存在路由鏈路，其中1i, j n+m，若1in表示i為傳感器節(jié)點，若n    進一步的，如果傳感器節(jié)點具有RSSI，可以根據(jù)射頻信號傳輸?shù)慕?jīng)驗?zāi)Ｐ凸烙嬫溌肪嚯xdij，同樣將估計距離發(fā)往網(wǎng)關(guān)節(jié)點。與連接矩陣L類似可以生成對稱距離矩陣，表示為D(n+m,n+m)，其中

9、Dij=Dji 表示i, j節(jié)點間路由鏈路的估計距離。    下一步就是根據(jù)連接矩陣L或距離矩陣D來進行節(jié)點定位。這里就需要用到MDS算法，MDS算法的全稱是多維標度分析（Multi-DimensionalScaling），是一種最早應(yīng)用在計量心理學(xué)和生物信息統(tǒng)計中的算法。作為MDS算法的一種簡單的應(yīng)用，若已知二維空間上n個點的兩兩距離，即完全的距離矩陣LALL(n,n)，則可以反解出這n個點的二維相對拓撲。YiShang等人8最早將MDS算法應(yīng)用到無線網(wǎng)絡(luò)定位中，本文也采用了類似的思路。由于通過路由過程獲得的連接矩陣L或距離矩陣D都只是部分鏈路，所以還需要通過最短路徑算法生成在原矩陣中不連通的節(jié)點之間的近似距離，得到近似的DALL來作為MDS