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

3.算法實(shí)現(xiàn)過程

3.1定向擴(kuò)散

目的是盡可能多的攜帶節(jié)點(diǎn)間的連接或測(cè)距信息，在建立梯度階段中，每個(gè)節(jié)點(diǎn)可以得到其下一跳節(jié)點(diǎn)ID。在傳輸數(shù)據(jù)階段，則將下一跳節(jié)點(diǎn)ID也打入數(shù)據(jù)包，按照最大梯度方向發(fā)往網(wǎng)關(guān)節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)具有RSSI時(shí)，還要將下一跳節(jié)點(diǎn)對(duì)應(yīng)的測(cè)距結(jié)果發(fā)往網(wǎng)關(guān)節(jié)點(diǎn)。

3.2計(jì)算節(jié)點(diǎn)距離矩陣DALL

目的是提取網(wǎng)關(guān)數(shù)據(jù)中關(guān)于節(jié)點(diǎn)連接或測(cè)距的信息，并通過最短路徑算法得到所有節(jié)點(diǎn)間的近似距離，即完全的距離矩陣。當(dāng)節(jié)點(diǎn)具有RSSI時(shí)，則可以根據(jù)數(shù)據(jù)包中的每個(gè)節(jié)點(diǎn)的測(cè)距信息生成部分距離矩陣D，然后采用Floyd最短路徑算法，生成DALL。若節(jié)點(diǎn)不具備RSSI，則將連通表示為單位距離1，同樣用Floyd最短路徑算法，由連接矩陣L生成DALL。

3.3多維標(biāo)度分析MDS

將節(jié)點(diǎn)距離矩陣DALL作為MDS算法的輸入矩陣，可以獲得節(jié)點(diǎn)的相對(duì)位置估計(jì)X’,Y’。

3.4平移和旋轉(zhuǎn)變換

通過比對(duì)已知位置的網(wǎng)關(guān)節(jié)點(diǎn)，將MDS結(jié)果進(jìn)行坐標(biāo)變換使得網(wǎng)關(guān)位置均方誤差最小。即設(shè)X’,Y’為MDS輸出的網(wǎng)關(guān)節(jié)點(diǎn)位置，求變換矩陣A,B使得[X’’,Y’’] = A * [X’, Y’] + B與網(wǎng)關(guān)節(jié)點(diǎn)已知位置[X, Y]的均方誤差最小。

4.仿真結(jié)果和分析

算法仿真采用Matlab6.5，仿真場(chǎng)景為100個(gè)傳感器節(jié)點(diǎn)隨機(jī)均勻分布在半徑50m的圓型區(qū)域內(nèi)，網(wǎng)絡(luò)中有大于等于三個(gè)已知位置的網(wǎng)關(guān)節(jié)點(diǎn)。

在圖2的仿真中，10個(gè)網(wǎng)關(guān)節(jié)點(diǎn)均勻分布在半徑為10米的圓周上，射頻通信距離取20m，射頻信號(hào)測(cè)距誤差為20%，圖中線段長(zhǎng)度代表定位誤差大小。仿真結(jié)果直觀的給出了RBSL算法在節(jié)點(diǎn)具有RSSI和沒有RSSI情況下定位的效果。從圖2的仿真中，還可以發(fā)現(xiàn)RBSL算法的一個(gè)應(yīng)用場(chǎng)景，即在大范圍的數(shù)據(jù)采集中，如果只有一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)，可以通過數(shù)據(jù)采集員手持一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)在一個(gè)小范圍內(nèi)移動(dòng)，在不同位置采集數(shù)據(jù)就可以對(duì)節(jié)點(diǎn)進(jìn)行定位。

圖3-a給出了節(jié)點(diǎn)RSSI測(cè)距誤差對(duì)結(jié)果的影響，可以發(fā)現(xiàn)，當(dāng)測(cè)距誤差在20%以內(nèi)時(shí)，定位結(jié)果較好，而若測(cè)距誤差進(jìn)一步增大，則結(jié)果惡化較為明顯。圖3-b給出了節(jié)點(diǎn)通信距離對(duì)結(jié)果的影響，可以發(fā)現(xiàn)在通信距離=25m時(shí)定位誤差最低，這是因?yàn)橥ㄐ啪嚯x過短會(huì)使得部分邊緣節(jié)點(diǎn)只有很少的鄰居，從而導(dǎo)致這些節(jié)點(diǎn)定位精度很低，而當(dāng)通信距離過長(zhǎng)時(shí)，網(wǎng)絡(luò)中的路由鏈路變少，導(dǎo)致能獲得鏈路信息變少，同樣降低了定位精度。

5.結(jié)論和研究展望

針對(duì)無線傳感器網(wǎng)絡(luò)的大范圍數(shù)據(jù)采集應(yīng)用場(chǎng)景，本文作者提出了基于路由信息的傳感器網(wǎng)絡(luò)定位算法RBSL。RBSL算法的主要優(yōu)點(diǎn)是通信開銷小，只需要每個(gè)節(jié)點(diǎn)在自身數(shù)據(jù)包上附加幾字節(jié)的信息，且容易實(shí)現(xiàn)，在大范圍的數(shù)據(jù)采集場(chǎng)景，只需要多個(gè)網(wǎng)關(guān)節(jié)點(diǎn)或一個(gè)可移動(dòng)的網(wǎng)關(guān)節(jié)點(diǎn)就可以獲得節(jié)點(diǎn)的定位結(jié)果。RBSL算法存在的問題是計(jì)算量較大，MDS和Floyd最短路徑算法復(fù)雜度均為O(n3)。但因在數(shù)據(jù)采集場(chǎng)景下，執(zhí)行計(jì)算任務(wù)的是網(wǎng)關(guān)PC節(jié)點(diǎn)，因此計(jì)算量的問題相對(duì)是可以接受的。此外，在前面的分析中假設(shè)網(wǎng)絡(luò)均勻同構(gòu)，事實(shí)上傳感器節(jié)點(diǎn)性能可能并不相同，且由于地形等因素影響也會(huì)造成網(wǎng)絡(luò)的不均勻，反映在RBSL算法中就是節(jié)點(diǎn)間測(cè)距結(jié)果精度的不同，如何在MDS算法中對(duì)精度不同的測(cè)距結(jié)果進(jìn)行加權(quán)是下一步的研究任務(wù)之一。

作者所在的清華大學(xué)電子工程系復(fù)雜系統(tǒng)工程實(shí)驗(yàn)室(CESL,ComplexEngineering System Lab)已經(jīng)自主開發(fā)了“靈活的低成本無線傳感器網(wǎng)絡(luò)平臺(tái)”，即FLOWS (Flexible Low-cOst Wireless Sensor network platform)。我們正在進(jìn)行FLOWS系統(tǒng)在智能大廈定位系統(tǒng)的研究與開發(fā)，相信會(huì)有很好的應(yīng)用前景和經(jīng)濟(jì)效益。