于 泉，徐保國

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122）

無線傳感器網(wǎng)絡(luò)節(jié)點定位研究受到國內(nèi)外學(xué)者的廣泛關(guān)注，根據(jù)定位時是否需要測量距離，定位算法可分為基于測距（Range—Based）算法和無需測距（Range—free）算法[1]。 基于測距的定位算法利用測量的距離或角度信息等進行定位運算，常用的測距技術(shù)主要有 RSSI[2]、TOA、TDOA、AOA[3]，無需測距通常根據(jù)網(wǎng)絡(luò)連通性進行定位，無需測距的算法主要有質(zhì)心算法、DV－Hop算法、APIT算法、MDS算法。基于測距的定位算法需要附加的設(shè)備，提高了設(shè)備成本和通信開銷大，無需測距算法由于對設(shè)備要求低，計算簡單和通信開銷小等優(yōu)點，成為無線傳感器網(wǎng)絡(luò)定位研究的熱點。無需測距定位的算法因在成本、功耗等方面的優(yōu)勢，受到越來越多的關(guān)注。

1 傳統(tǒng)定位算法模型

1.1 傳統(tǒng)質(zhì)心算法

南加州大學(xué)的Nirupama Bulusu等人[4]提出一種基于網(wǎng)絡(luò)連通性無需測距的質(zhì)心定位算法，主要思路舉例體現(xiàn)，假設(shè)未知節(jié)點F在A1…An為錨節(jié)點組成的多邊形中，錨節(jié)點坐標分別為（x1，y1）～（yn，yn），則未知節(jié)點 F 坐標為：

傳統(tǒng)質(zhì)心算法的計算量和通信開銷較少，原理簡單容易實現(xiàn)，受到廣泛研究，但其對傳感器節(jié)點密度和均勻度依賴強，質(zhì)心算法受這兩個因素影響較大，當(dāng)錨節(jié)點接受的信息方差較大時，定位精度會變得比較低，定位精度有待提升，文獻[5]提出了基于RSSI的三角形質(zhì)心算法，三角形面積減小，定位精度得到一定提升；文獻[6]利用三角形三邊的垂直平分線，劃分6個區(qū)域，通過比較三錨節(jié)點接收的信號強度，確定未知節(jié)點所在的區(qū)域；上述算法都是通過縮小未知節(jié)點所在三角形的面積，提高定位的精度，本文思路大致相同，通過連接三邊中點劃分16或10個區(qū)域，利用外心的適應(yīng)度值大小確定未知節(jié)點所在區(qū)域，同樣提升了定位精度。

1.2 RSSI測距技術(shù)

RSSI的測距，接收節(jié)點根據(jù)收到信號強度，計算信號傳輸損耗，利用信號的經(jīng)驗?zāi)Ｐ突蚶碚撃Ｐ蛯鬏敁p耗轉(zhuǎn)化為距離[7]。信號的經(jīng)驗?zāi)Ｐ褪瞧ヅ浣⒃诟鱾€點上的位置與信號強度的數(shù)據(jù)庫，理論模型通常采用的是無線電傳播損耗模型，常用的傳播路徑損耗模型有：對數(shù)－常態(tài)分布模型和自由空間無線電傳播路徑損耗模型，采用對數(shù)－常態(tài)分布模型[8]，即

其中，PL（d）為信號傳輸距離 d 的路徑損耗，PL（do）為信號傳輸距離do的路徑損耗，n為信號衰減參數(shù)，通常取2～5，Xσ為期望為0標準差為σ的高斯分布。未知節(jié)點接收到錨節(jié)點信號強度為：

2 改進的三角形質(zhì)心算法

如圖1所示未知節(jié)點D在三個錨節(jié)點組成的銳角三角形內(nèi)，A1、A2、A3分別為 AB、AC、BC 的中點， 則 4 個小三角形兩兩全等，外接圓的半徑也相同，假設(shè)點D是兩平行線A1A2、A4A5之間的任意一點，作DE垂直 A1A2，則∠P1DE為鈍角，連接 P1E、P2E，點 O 為 A1A2的中點，連接 P1O、P2O，P1、P2分別為三角形A A1A2和三角形A1A2A3的外心，圓心到弦中點的直線垂直平分弦，即P1O、P2O垂直平分A1A2，所以，P1E=P2E，因為∠P1DE為鈍角，所以P1E>P1D，所以P1E>P1D，即點D到三角形A A1A2的外心比到三角形A1A2A3的外心距離要小，三角形內(nèi)的其他點，即三角形A A3A4內(nèi)的點，到P1的距離明顯比到P2的距離小，得出三角形A A1A2內(nèi)的點到外心的距離中，到P1的距離最小。其它相鄰三角形的判斷與上述同理，判斷未知節(jié)點在錨節(jié)點組成的三角形內(nèi)后，連接三邊中點，計算小三角形的外心，然后比較未知節(jié)點到四個外心的距離，得到距離最近的外心，它所在的小三角形就是未知節(jié)點所在區(qū)域，繼續(xù)按此原理劃分區(qū)域，最終把三角形劃分了16個區(qū)域，通過判斷未知節(jié)點到哪一外心距離最小，來判斷其所在的小三角形，但是未知節(jié)點坐標未知，無法計算其到外心的距離，受到定位算法中適應(yīng)度值[9]計算的啟發(fā)，距離未知節(jié)點越近，適應(yīng)度越小，確定未知節(jié)點所在小三角形后，得到小三角形質(zhì)心，質(zhì)心為未知節(jié)點估計坐標。

適應(yīng)度值計算公式為：

式中：（xj，yj）為小三角形的外心坐標，（xi，yi）為 i錨節(jié)點坐標，di為未知節(jié)點到i錨節(jié)點的距離，n為錨節(jié)點數(shù)量。

所有患者均給予常規(guī)對癥治療,吸氧、服用阿司匹林、阿托伐他汀,控制血壓、血糖,根據(jù)顱內(nèi)壓情況酌情給予甘露醇脫水治療,并給予改善微循環(huán)、抗感染維持水、電解質(zhì)平衡等治療。在此基礎(chǔ)上,對照組給予依達拉奉注射液(吉林省輝南長龍生化藥業(yè)股份有限公司,國藥準字H20080592)30 mg加入生理鹽水100 m L中靜脈滴注,2次/d。觀察組在對照組基礎(chǔ)上服用丁苯酞軟膠囊(石藥集團恩必普藥業(yè)有限公司,國藥準字H20050299)0.2 g/次,3次/d。14 d為1個療程,1個療程后評價療效[3]。

未知節(jié)點在三錨節(jié)點組成的直角三角形時，連接三邊中點，其中兩個小三角形的外心重合，先判斷這3個外心適應(yīng)度值最小者。如果重合的外心適應(yīng)度值最小，把所在的區(qū)域縮小為矩形區(qū)域，再把矩形區(qū)域平分成4個小矩形，求出其外心坐標及其適應(yīng)度值，得到適應(yīng)度值最小的外心，相應(yīng)的小矩形的質(zhì)心為估計位置。如果另外兩個小三角形外心適應(yīng)度值最小，連接三邊中點，重合外心的兩個小三角形作為一個區(qū)域參與判斷，最終直角三角形被分成10個三角形或矩形，如圖2所示，P1～P10為10個三角形或矩形的外心，若頂點A、B、C坐標后計算P1～P10的適應(yīng)度值，判斷未知節(jié)點在哪一小三角形后，求出三角形的質(zhì)心，質(zhì)心則為未知節(jié)點的估計坐標。

圖1 未知節(jié)點在銳角三角形中Fig.1 The unknown node in acute triangle

圖2 未知節(jié)點在直角三角形中Fig.2 The unknown node in right triangle

未知節(jié)點在3個錨節(jié)點組成的鈍角三角形中時，與銳角三角形情況不同的是，兩個小三角形的外心在相鄰的三角形中，如圖3所示，D、E分別為三角形P1P2P3、P1B P3的外心，未知節(jié)點F在三角形P1B P3內(nèi)，距離三角形P1B2P3的外心最近，未知節(jié)點F在三角形P1P2P3內(nèi)時，距離三角形P1B P3的外心最近。先判斷三角形P1A P2、P2CP3、P1P2P3外心的適應(yīng)度值，若判斷未知節(jié)點在三角形P1P2P3內(nèi)，未知節(jié)點也可能在三角形P1B P3內(nèi)，再比較外心D、E的適應(yīng)度值，若D適應(yīng)度值小，未知節(jié)點在三角形P1BP3內(nèi)，若E適應(yīng)度值最小，未知節(jié)點在三角形P1P2P3內(nèi)，連接三邊中點，繼續(xù)劃分小三角形。若未知節(jié)點在三角形P1A P3或三角形P1CP3內(nèi)，繼續(xù)連接中點劃分三角形，最終三角形被劃分為16個小三角形。

在100×100 m矩形區(qū)域隨機分布50個傳感器節(jié)點，取其中一個作為參考點，取距離參考節(jié)點h的圓上點，從弧度0～6.2選取63個點，得到適應(yīng)度值曲線，如圖4所示，距離未知節(jié)點相同的適應(yīng)度值是波動的，并不是恒定不變的，距離相差大的時候，距離越小適應(yīng)度值越小，但是當(dāng)距離相差不大時，適應(yīng)度值曲線會有交點，距離大的適應(yīng)度值不一定大，存在一定誤差，會造成上述判斷錯誤，降低定位精度。

圖3 未知節(jié)點在鈍角三角形中Fig.3 The unknown node in obtuse triangle

圖4 距離不同的適應(yīng)度值曲線Fig.4 Fitness value curve in different distance

以一個銳角三角形特列仿真實驗，三角形面積為32 m2，在三角形內(nèi)隨機取100個點，驗證算法是否準確，實驗100次取平均，求得判斷準確率為30.25%，造成誤差的主要原因是距離不變時適應(yīng)度值不穩(wěn)定，會造成判斷所在的小三角形和實際所在的小三角形不同，由于只有在距離相差少時才會造成判斷錯誤，所以兩個小三角形往往是鄰居，上述的銳角三角形特例實驗中，也得出了定位誤差小于1 m的點達到80.63%，判斷誤差一定程度上提高了定位精度，說明本算法的可行性。

3 算法步驟

1）錨節(jié)點向周圍環(huán)境周期性廣播包含自身ID和位置坐標的信息。

2）未知節(jié)點收到錨節(jié)點廣播的信息后，對同一個錨節(jié)點的RSSI值[11]，取多個RSSI數(shù)據(jù)的均值，作為其接收的RSSI值；

3）未知節(jié)點接收錨節(jié)點廣播的信號，并建立3個集合:錨節(jié)點集合：B_Set={b1，b2，…，bn}；未知節(jié)點到錨節(jié)點距離集合：D_Set={d1，d2， …，dn}； 錨節(jié)點位置集合：P_Set={（x1，y1），（x2，y2），…（xn，yn）}；

4）未知節(jié)點從集合中選擇距離未知節(jié)點小于通信半徑R的錨節(jié)點，然后從選取的錨節(jié)點中任意選擇三個組成三角形，構(gòu)成一個3角形集合，分別采用添加計數(shù)器的PIT測試[10]，選出內(nèi)含未知節(jié)點的三角形集合，記為：T_Set={（b1，b2，b3），（bi，bj，bk）…}，若選取的錨節(jié)點數(shù)小于 3，利用傳統(tǒng)質(zhì)心算法來定位；

5）判斷三角形是銳角三角形、直角三角形或鈍角三角形，然后分別采用上述方法求出未知節(jié)點的坐標集{（xe1，xe1），（xe2，xe2）…（xep，xep）}。

6）取坐標集合{（xe1，xe1），（xe2，xe2）…（xep，xep）}的期望，即其中，（x，y） 是未知節(jié)點的坐標。

4 仿真結(jié)果及分析

通過Matlab R2010b進行仿真，同時仿真?zhèn)鹘y(tǒng)質(zhì)心算法和本文優(yōu)化的三角形質(zhì)心算法，來驗證算法的性能。評估算法性能指標為平均定位誤差。

其中定位誤差為：

式中：（x，y）為算法估計未知節(jié)點 i的坐標，（xi，yi）為未知節(jié)點i的真實坐標。

平均定位誤差為：

式中：n為未知節(jié)點數(shù)量，R為通信半徑。

節(jié)點分布越均勻、密度越大，定位精度越高，每次實驗的均勻度和密度不同，這些因素會影響實驗結(jié)果，因此實驗100次取平均值更合理，更能體現(xiàn)算法的定位效果。如圖5所示，傳感器節(jié)點數(shù)量50，通信半徑20 m，調(diào)節(jié)錨節(jié)點比列，錨節(jié)點比例越大平均定位誤差越小，本文算法的平均定位誤差降低了15.47%。如圖6所示，錨節(jié)點比例保持40%、通信半徑20 m，傳感器節(jié)點越多平均定位誤差越小，本文算法的平均定位誤差降低了15.21%，最高降低了17.80%。如圖7所示，傳感器節(jié)點50，錨節(jié)點20個，調(diào)節(jié)通信半徑，本文算法的平均定位誤差降低了11.70%，通信半徑越大，兩者定位誤差差距有擴大趨勢。上述實驗表明錨節(jié)點比例越大、傳感器節(jié)點數(shù)量越多、通信半徑下越大，平均定位誤差越小，本文算法的定位精度提升明顯。

圖5 錨節(jié)點比例不同時的誤差Fig.5 Error of different anchor node proportion

如圖8所示，在60×60 m矩形區(qū)域中隨機分布50個傳感器節(jié)點，錨節(jié)點25個，通信半徑20 m，圖示25個未知節(jié)點的誤差圖，傳統(tǒng)質(zhì)心算法節(jié)點誤差的期望為11.479 4 m，方差為38.030 1，本文算法的節(jié)點誤差期望為6.606 4 m，方差為29.007 2?？梢钥闯?，本文算法相比傳統(tǒng)質(zhì)心算法精度提升明顯，穩(wěn)定性也得到了一定的提高。

圖6 節(jié)點數(shù)量不同時的誤差Fig.6 Error of different number of nodes

圖7 通信半徑不同時的誤差Fig.7 Error of different communication radius

圖8 節(jié)點誤差圖Fig.8 Node error figure

5 結(jié) 論

傳統(tǒng)質(zhì)心算法計算簡單、通信開銷少，但對網(wǎng)絡(luò)環(huán)境依賴程度較高，定位精度也有待提升，本文算法把內(nèi)含未知節(jié)點的三角形劃分16或10個區(qū)域，利用外心適應(yīng)度值的大小，來確定未知節(jié)點所在區(qū)域，三角形面積減小，定位精度變高，通過matlab仿真得出：本文算法的定位精度提升明顯，平均定位誤差最高降低了17.80%，穩(wěn)定性也得到一定提升。

[1]劉鋒，章登義．基于RSSI的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J]．計算機科學(xué)，2012，39（6A）：96-98.LI Feng，ZHANG Deng-yi. The centroid localization algorithm based on RSSI for Wireless sensor network[J].Computer Science，2012，39（6A）:96-98.

[2]Lu thy K A，E Grant D，Henderson T C.Leveraging RSSI for Robotic Repair of D is connected Wireless Sensor Networks[C]//Proceedings of 2007 IEEE In tern at ion al Conference on Robotics and Automation.Rome， Italy，2007:10-14.

[3]劉姍，冷文，王安國，等.一種基于RSSI的AOA估計算法[J].傳感器與微系統(tǒng)，2013，32（11）：132-134.LIU Shan，LENG Wen，WANG An-guo，et al.An AOA estimation algorithm based on RSSI[J].Transducer and Microsystem Technologies，2013，32（11）:132-134.

[4]Nirupama Bulusu，John Heidemann，Deborah Estrin.Adaptive Beacon Placement[C]//In Proceedings of the 21st International Conference on Distributed Computing Systems.Mesa:[s.n.]，2001:489-498.

[5]林瑋，陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J]．現(xiàn)代電子技術(shù)，2009，289（2）：180-182.LINWei，CHENChuan-feng.The triangle centroid localization algorithm based on RSSI for wireless sensor network[J].Modern Electronic Technology，2009，289（2）:180-182.

[6]Yu Liu，Xiao Yi，You He．A Novel Centroid Localization for Wireless Sensor Networks [J].International Journal of Distributed Sensor Networks，2012，2012：1-8．

[7]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[8]孫懋珩，廖根?。甒SNs中基于粒子群優(yōu)化的節(jié)點定位算法[J].測控技術(shù)，2011，30（12）：111-115.SUN Mao-hang，LIAO Gen-jian.Node localization algorithm based on particle swarm optimization In WSNs[J].Measurement and Control Technology，2011，30（12）:111-115.

[9]李牧東，熊偉，梁青.基于人工蜂群改進算法的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報，2013，26（2）：241-245.LI Mu-dong，XIONG Wei，LIANG Qing.Wireless sensor networks node localization algorithm based on improved ABC algorithm[J].Chinese Journal of Sensors and Actuators，2013，26（2）:241-245.

[10]王新生，廖世奇.基于區(qū)域分割的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機應(yīng)用與軟件，2013，30（4）：231-234.WANG Xin-sheng，LIAO Shi-qi.Wireless sensor network localization algorithm based on region segmentation[J].Computer Applications and Software，2013，30（4）:231-234.

[11]張錚，饒志訓(xùn)，黃志峰.無線傳感器網(wǎng)絡(luò)中RSSI濾波的若干處理方法[J].現(xiàn)代電子技術(shù),2013(20):4-6,10.ZHANGZheng，RAOZhi-xun，HUANGZhi-feng.Someprocessing methods of RSSI filtering in wireless sensor network[J].Modern Electronics Technique，2013（20）:4-6，10.