基于機會網(wǎng)絡(luò)節(jié)點定位算法的優(yōu)化設(shè)計

劉 濤

（阜陽職業(yè)技術(shù)學(xué)院 工程科技學(xué)院，安徽 阜陽 236031）

0 引言

節(jié)點定位技術(shù)是機會網(wǎng)絡(luò)主要支撐技術(shù)，國內(nèi)外對該技術(shù)的研究滲透到了移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、計算機網(wǎng)絡(luò)等多個領(lǐng)域，也出現(xiàn)了比較多的新思路和新算法，但節(jié)點定位的 “安全” “準(zhǔn)確” “廣泛” 的特征很大程度上決定了技術(shù)推廣的實際價值.因此，龍增艷等［1］提出機會網(wǎng)絡(luò)中的節(jié)點數(shù)據(jù)在轉(zhuǎn)發(fā)數(shù)據(jù)包之前，利用探測的方式來發(fā)現(xiàn)自身節(jié)點與其他節(jié)點的連接點，需要一種均衡關(guān)系來滿足這一要求.劉名陽等［2］提出，隨著無線網(wǎng)絡(luò)的普及與發(fā)展，不同移動網(wǎng)絡(luò)的路由節(jié)點自主性提高，在此基礎(chǔ)上，網(wǎng)絡(luò)安全以及網(wǎng)絡(luò)定位成為機會網(wǎng)絡(luò)研究的重要一環(huán).張光華等［3］提出，機會網(wǎng)絡(luò)中的自私節(jié)點是影響網(wǎng)絡(luò)安全輸出數(shù)據(jù)的重要因素，建立可信的路由模型是構(gòu)建網(wǎng)絡(luò)安全的一項重要手段.綜上所述，網(wǎng)絡(luò)節(jié)點定位問題是機會網(wǎng)絡(luò)構(gòu)建的核心問題，而如何解決節(jié)點定位覆蓋率低這一問題更是重中之重.本文正是基于原有的經(jīng)典APIT 算法做了相應(yīng)改進(jìn)，得到基于內(nèi)點測試法的加權(quán)質(zhì)心定位改進(jìn)算法，該算法的擴展性能比APIT 算法更強，節(jié)點定位精度和覆蓋率也較原先的算法大幅提高，可以滿足大中型規(guī)模的機會網(wǎng)絡(luò)中較低的定位誤差和較高的節(jié)點定位覆蓋率的要求.

1 基于內(nèi)點測試的改進(jìn)算法

原有的經(jīng)典APIT算法存在一些問題，為了解決原有算法的問題，提出了優(yōu)化算法.優(yōu)化算法利用內(nèi)點測試法判斷未知節(jié)點與其鄰居錨節(jié)點的位置關(guān)系，從而縮小未知節(jié)點可能所處的范圍，再利用加權(quán)質(zhì)心算法對未知節(jié)點進(jìn)行定位.

1.1 內(nèi)點測試法

假如節(jié)點的移動存在一個方向，沿著這個方向節(jié)點D同時遠(yuǎn)離或靠近三角形的三個端點A，B，C，那么可以判定節(jié)點D 位于△ABC 之外，如圖1（a）所示；否則，當(dāng)節(jié)點D 遠(yuǎn)離其中兩個節(jié)點并且靠近另一個節(jié)點，或者靠近兩個節(jié)點并且遠(yuǎn)離另一個節(jié)點時，則判定節(jié)點D位于△ABC內(nèi)，如圖1（b）所示.

圖1 內(nèi)點測試法原理圖

這里的內(nèi)點測試法是利用信號的傳播特性來判斷未知節(jié)點是否遠(yuǎn)離或靠近的.本文假設(shè)節(jié)點間發(fā)射信號強度與距離滿足式（1）的通用模型：

其中：PR為節(jié)點接收到的信號強度；PT為發(fā)射功率；W(d0)為經(jīng)過距離d0的路徑損耗；η 為路徑損耗指數(shù)；d為距離.通常節(jié)點信號源距離未知節(jié)點越遠(yuǎn)，未知節(jié)點接收到的能量信號越弱.

1.2 基于兩個錨節(jié)點定位方法

在機會網(wǎng)絡(luò)中經(jīng)常會遇到這樣的情況：節(jié)點是移動的，當(dāng)未知節(jié)點只有兩個鄰居錨節(jié)點時，可以通過一定的數(shù)學(xué)計算來得到它的位置坐標(biāo)［4］.設(shè)A，B是它的兩個鄰居錨節(jié)點.錨節(jié)點A，B的坐標(biāo)是已知的，未知節(jié)點S的坐標(biāo)為(xs,ys).通過信號強度與距離轉(zhuǎn)換模型式（1），可以得到AS，BS，AB 之間的距離，它們分別用d1，d2，d3表示，那么在△ABS中作AB的高SC，SF⊥x軸，CE⊥x軸，BD⊥x軸，如圖2所示.

圖2 基于兩個錨節(jié)點的定位

設(shè)∠SAB = α，∠BAD = β，根據(jù)正余弦定理得到

所以

導(dǎo)出

同理，結(jié)合錨節(jié)點B的坐標(biāo)和正余弦定理，易知

又

計算未知節(jié)點坐標(biāo)為

2 實驗仿真結(jié)果與分析

2.1 同一錨節(jié)點比例

在網(wǎng)絡(luò)環(huán)境部署完成的情況下，現(xiàn)保持錨節(jié)點比例為30%不變，節(jié)點總數(shù)分別為100，110，120，130和140個.仿真情況如圖3所示.

圖3 同一錨節(jié)點比例統(tǒng)計

由圖3（a）可見，在錨節(jié)點比例不變的情況下，本文算法比傳統(tǒng)APIT算法體現(xiàn)出更小的定位誤差.隨著總結(jié)點個數(shù)的增加，定位誤差接近0.3%，而APIT算法的定位誤差卻保持在0.45%左右，這說明了本文算法比APIT算法優(yōu)越，比較適合大規(guī)模的網(wǎng)絡(luò)節(jié)點定位［5］.由圖3（b）可見，APIT算法的定位覆蓋率維持在70%左右.而本文算法隨著節(jié)點總數(shù)的增加，定位覆蓋率不斷接近100%，這說明當(dāng)錨節(jié)點比例不變時，本文算法在定位覆蓋率方面略勝一籌.

2.2 不同錨節(jié)點比例

考慮錨節(jié)點比例不同的情況.設(shè)節(jié)點總數(shù)為100，不同的錨節(jié)點數(shù)分別為20，30，40，50，60 等，兩種算法的定位精度和定位覆蓋率的變化情況如圖4所示.

由圖4（a）可見，隨著錨節(jié)點個數(shù)的增多，APIT 算法的定位誤差越來越差，最差可達(dá)到0.6%，這說明APIT算法中，未知節(jié)點定位時受到錨節(jié)點的影響較大，尤其是相距未知節(jié)點較遠(yuǎn)的鄰居錨節(jié)點，這樣會使質(zhì)心估計時的誤差增大.而在本文算法中就不存在這樣的問題，錨節(jié)點個數(shù)增多對本文算法是有利的，即鄰居錨節(jié)點增多，在內(nèi)點測試階段，選擇距離未知節(jié)點最近的三角形的加權(quán)質(zhì)心作為估計位置，結(jié)果會更加準(zhǔn)確［6］.由圖4（b）可見，隨著錨節(jié)點個數(shù)增加，APIT 算法的節(jié)點定位覆蓋率呈現(xiàn)上升趨勢，而本文的算法的節(jié)點定位覆蓋率不斷接近100%.這說明錨節(jié)點個數(shù)增加時，本文算法比APIT算法性能更加優(yōu)越.

圖4 不同錨節(jié)點比例統(tǒng)計

2.3 不同的網(wǎng)絡(luò)連通度

比較兩種算法在不同的網(wǎng)絡(luò)連通度下的性能，通過改變節(jié)點通信半徑來實現(xiàn)網(wǎng)絡(luò)連通度的改變.通信半徑R分別取20，22，24，26，28 m，算法性能如圖5所示.

圖5 不同網(wǎng)絡(luò)連通度統(tǒng)計

由圖5（a）可見，當(dāng)通信半徑增大時，本文算法的定位誤差率與APIT 算法呈現(xiàn)不同的趨勢.傳統(tǒng)APIT 算法的定位誤差率存在上升勢頭，當(dāng)通信半徑增大到28 m 時，定位誤差率已經(jīng)達(dá)到0.48%.而本文算法的定位誤差率在緩慢下降，當(dāng)通信半徑增大到28 m 時，定位誤差率已經(jīng)接近0.28%，比APIT 算法低很多.由圖5（b）可見，當(dāng)增大通信半徑時，本文算法的節(jié)點定位覆蓋率一直呈現(xiàn)上升趨勢，不斷接近100%.

3 結(jié)語

本文根據(jù)機會網(wǎng)絡(luò)的網(wǎng)絡(luò)特性，一方面鑒于免測距定位算法易實現(xiàn)的優(yōu)點，另一方面結(jié)合內(nèi)點測試法和加權(quán)質(zhì)心算法，提出了定位精度、節(jié)點定位覆蓋率都比較高的新機會網(wǎng)絡(luò)節(jié)點定位算法.經(jīng)節(jié)點升級后的優(yōu)化算法相對于傳統(tǒng)的APIT算法更具精度高、誤差低、易實現(xiàn)等多方面的優(yōu)越性.