基于聚集共線度和節(jié)點(diǎn)連通度的無線傳感器網(wǎng)絡(luò)定位算法

黃 亮

(中國電子科技集團(tuán)公司 第二十八研究所，南京 210007)

(*通信作者電子郵箱huangliangnumber1@163.com)

黃 亮*

(中國電子科技集團(tuán)公司 第二十八研究所，南京 210007)

(*通信作者電子郵箱huangliangnumber1@163.com)

為進(jìn)一步提高無線傳感器網(wǎng)絡(luò)(WSN)的定位精度，對錨節(jié)點(diǎn)分布與網(wǎng)絡(luò)定位精度之間的關(guān)系進(jìn)行研究，提出一種新的基于“聚集-共線度”(DAC)和“節(jié)點(diǎn)度”(ND)的錨節(jié)點(diǎn)選擇算法——DAC-ND。首先，通過實(shí)驗(yàn)分析得出錨節(jié)點(diǎn)在共線分布和集中分布時(shí)對定位精度影響較大；然后，經(jīng)過對基于共線度的錨節(jié)點(diǎn)選擇算法進(jìn)行分析和比較，發(fā)現(xiàn)現(xiàn)有的基于最小角和最小高的兩類錨節(jié)點(diǎn)共線度算法(DC-A和DC-H)均存在不足；最后，綜合這兩類算法的優(yōu)勢提出一種新的基于“聚集-共線度”的概念，并結(jié)合“節(jié)點(diǎn)度”提出DAC-ND錨節(jié)點(diǎn)選擇算法。通過Matlab仿真實(shí)驗(yàn)得出，與錨節(jié)點(diǎn)隨機(jī)選擇算法相比，DAC-ND算法可大幅降低平均定位誤差(54%～73%)；與基于最小角和最小高的共線度選擇算法等相比，采用DAC-ND算法平均定位誤差可分別降低15%～23%和12%～23%。實(shí)驗(yàn)結(jié)果表明，DAC-ND算法相比DC-A和DC-H能夠獲得更高的定位精度，從而驗(yàn)證了DAC-ND算法的有效性。

無線傳感器網(wǎng)絡(luò)；定位；錨節(jié)點(diǎn)；共線度；節(jié)點(diǎn)度

0 引言

隨著無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)的發(fā)展和普及，傳感器網(wǎng)絡(luò)自身定位技術(shù)在應(yīng)用中顯得愈發(fā)重要。WSN定位技術(shù)通常可分為基于測距和無須測距兩種[1],其中基于測距技術(shù)的定位算法如三邊定位等由于定位精度較高，應(yīng)用最為廣泛。但由于測距方法本身存在一定誤差，如接收信號強(qiáng)度指示(Received Signal Strength Indication， RSSI)的測距誤差可能高達(dá)±50%，使得測量的距離信息并不準(zhǔn)確，進(jìn)而對定位算法的定位效果產(chǎn)生不良影響[2]。這種情況隨著高精度測距技術(shù)如到達(dá)時(shí)間差(Time Difference Of Arrival， TDOA)、飛行時(shí)間(Time Of Fly， TOF)等測距技術(shù)的發(fā)展而得到大幅改善。然而，除測距精度之外，在WSN定位算法中，因?yàn)檫x擇不恰當(dāng)?shù)腻^節(jié)點(diǎn)也可能會(huì)導(dǎo)致較大的定位誤差甚至定位失敗。在基于測距的多維定標(biāo)(Multi-Dimensional Scaling， MDS)定位算法中，如MDS-MAP[3]、等距特征映射 (ISOmetric feature MAPping, ISOMAP)[4-5]等，這類算法完全依賴錨節(jié)點(diǎn)將網(wǎng)絡(luò)相對坐標(biāo)轉(zhuǎn)換為絕對坐標(biāo)。因此如何選擇合適的錨節(jié)點(diǎn)便成為此類定位算法中的一個(gè)重要問題。

當(dāng)前研究人員普遍認(rèn)為選擇分布較均勻的錨節(jié)點(diǎn)進(jìn)行定位能夠提高WSN的定位精度[6-9]。為了充分認(rèn)識(shí)錨節(jié)點(diǎn)之間以及錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的分布或拓?fù)潢P(guān)系對WSN定位精度的影響，文獻(xiàn)[6]針對錨節(jié)點(diǎn)的部署或分布與算法定位精度的關(guān)系進(jìn)行分析并提出了錨節(jié)點(diǎn)的優(yōu)化部署策略；文獻(xiàn)[7]則針對傳感器網(wǎng)絡(luò)提出一種改進(jìn)的錨節(jié)點(diǎn)選擇策略以提高定位精度。文獻(xiàn)[8]和文獻(xiàn)[9]則引入了共線度(Degree of Collinearity， DC)的概念，并將其應(yīng)用到網(wǎng)絡(luò)節(jié)點(diǎn)定位中以避免較大的定位誤差。其中，文獻(xiàn)[8]將共線度用于衡量選擇的錨節(jié)點(diǎn)組合是否有效，并提出一種基于三角形最小高的“共線度”定義，即三個(gè)錨節(jié)點(diǎn)構(gòu)成的三角形中三個(gè)高的最小值；文獻(xiàn)[9]則提出了一種基于最小角的“共線度”的概念，并基于此提出一種基于共線度的無線傳感器網(wǎng)絡(luò)定位算法(Collinearity Based Localization Algorithm， CBLA)以提高定位精度。

基于共線度的定義，文獻(xiàn)[10]針對動(dòng)態(tài)傳感器網(wǎng)絡(luò)提出了一種基于共線限制因子(Collinearity Limiting Factor， CLF)的錨節(jié)點(diǎn)共線解決方案，CLF即錨節(jié)點(diǎn)組成三角形任意高與底邊的比值，該方法本質(zhì)上源自三角形最小高的共線度定義。受其影響，文獻(xiàn)[11]通過限制錨節(jié)點(diǎn)之間的角度大小給出了一種錨節(jié)點(diǎn)共線約束選擇策略，該方法本質(zhì)上則源自基于最小角的共線度定義。除此之外，Zhang等[12]基于共線度改進(jìn)DV-Hop(Distance Vector-Hop)定位算法定位精度；文獻(xiàn)[13]則研究了2維、3維空間網(wǎng)絡(luò)節(jié)點(diǎn)定位估計(jì)中的共線、共面問題，并通過對錨節(jié)點(diǎn)位置幾何拓?fù)潢P(guān)系的研究提出了基于拓?fù)滟|(zhì)量的解決方案。

然而，目前尚無研究對這兩類基于最小高和最小角的共線度定義及相關(guān)的定位算法進(jìn)行比較。本文對這兩種基于不同共線度定義的算法的缺陷進(jìn)行分析，引出“聚集-共線度”(Degree of Aggregation-Collinearity, DAC)概念，并在此基礎(chǔ)上提出一種基于“聚集-共線度”和“節(jié)點(diǎn)度”的錨節(jié)點(diǎn)選擇策略以提高定位精度，稱為DAC-ND。最后通過Matlab仿真實(shí)驗(yàn)與基于共線度的定位算法進(jìn)行對比驗(yàn)證。

1 錨節(jié)點(diǎn)分布對定位精度的影響

在對MDS、ISOMAP等定位算法的實(shí)驗(yàn)分析中，如何選擇合適的錨節(jié)點(diǎn)成為制約此類算法定位精度的一個(gè)非常重要的因素，因此對其進(jìn)行專門分析。通過實(shí)驗(yàn)分析可知，當(dāng)所選擇的錨節(jié)點(diǎn)組合在共線分布和集中分布兩種情況下時(shí)會(huì)導(dǎo)致定位結(jié)果出現(xiàn)較大的誤差，下面將通過實(shí)驗(yàn)結(jié)果來具體說明錨節(jié)點(diǎn)分布對定位結(jié)果的影響。在仿真實(shí)驗(yàn)中，選擇MDS定位算法中最早也是最為常用的MDS-MAP[3-4]作為實(shí)驗(yàn)對象，在50 m×50 m的二維平面隨機(jī)部署15個(gè)節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)通信半徑R=30 m，鄰居節(jié)點(diǎn)間距離可測且不考慮測距誤差以便觀察問題現(xiàn)象。

1.1 錨節(jié)點(diǎn)共線分布

在隨機(jī)部署的包含15個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，假設(shè)其中{2,5,7,12,13}為坐標(biāo)已知節(jié)點(diǎn)，并從中隨機(jī)選擇三個(gè)作為錨節(jié)點(diǎn)，其余節(jié)點(diǎn)均為坐標(biāo)未知節(jié)點(diǎn)。那么在仿真實(shí)驗(yàn)結(jié)果中會(huì)出現(xiàn)如圖1、2所示的兩種極端情況。

圖1表示選擇錨節(jié)點(diǎn)組合{2,12,13}時(shí)MDS-MAP算法的定位計(jì)算結(jié)果與真實(shí)絕對坐標(biāo)的對比，此時(shí)三個(gè)錨節(jié)點(diǎn){2,12,13}的分布構(gòu)成一個(gè)較為均勻的三角形，圖1(a)和(b)的形狀幾乎完全相同，所有網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)的平均定位誤差僅為0.31 m，在所有錨節(jié)點(diǎn)組合中定位精度最高。

圖2表示選擇錨節(jié)點(diǎn)組合為{2,5,7}時(shí)MDS-MAP算法的定位計(jì)算結(jié)果與真實(shí)絕對坐標(biāo)的對比，此時(shí)定位算法結(jié)果誤差非常大，平均定位誤差達(dá)到36.34 m，比選擇錨節(jié)點(diǎn)組合{2,12,13}所得最小定位誤差增大近117倍，高出兩個(gè)數(shù)量級。通過觀察可發(fā)現(xiàn)，錨節(jié)點(diǎn){2,5,7}近似共線。

圖1 選擇均勻分布錨節(jié)點(diǎn)組合{2,12,13}

圖2 選擇近似共線錨節(jié)點(diǎn)組合{2,5,7}時(shí)的定位結(jié)果與真實(shí)坐標(biāo)對比

通過多次重復(fù)實(shí)驗(yàn)統(tǒng)計(jì)可知，錨節(jié)點(diǎn)均勻分布時(shí)定位算法具有較好的定位精度，而錨節(jié)點(diǎn)共線或近似共線則會(huì)導(dǎo)致定位算法出現(xiàn)極大的定位誤差。

1.2 錨節(jié)點(diǎn)集中分布

同樣隨機(jī)部署15個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，其中{2,5,7,12,13}為坐標(biāo)已知節(jié)點(diǎn)，其余均為坐標(biāo)未知節(jié)點(diǎn)。

圖3為選擇錨節(jié)點(diǎn){2,5,7}定位的結(jié)果示意圖，這組錨節(jié)點(diǎn)的分布構(gòu)成一個(gè)較為均勻的三角形，圖3(a)和(b)的形狀大致相似，此時(shí)算法平均定位誤差約0.77 m。

圖3 選擇均勻分布錨節(jié)點(diǎn)組合{2,5,7}時(shí)的定位結(jié)果與真實(shí)坐標(biāo)對比

圖4為選擇錨節(jié)點(diǎn){2,12,13}進(jìn)行定位的結(jié)果，圖4(a)和(b)的形狀存在較大差異，部分節(jié)點(diǎn)位置發(fā)生較大偏移超出圖片范圍之外。觀察可知，所選三個(gè)錨節(jié)點(diǎn)分布太過集中，算法的定位結(jié)果誤差達(dá)到8.47 m，與選擇錨節(jié)點(diǎn)組合{2,5,7}所得最小定位誤差相比，提高了一個(gè)數(shù)量級，誤差增大10多倍。

圖4 選擇集中分布錨節(jié)點(diǎn)組合{2,12,13}

通過以上兩個(gè)實(shí)驗(yàn)的對比結(jié)果可知，WSN定位算法中的錨節(jié)點(diǎn)的分布對定位結(jié)果的誤差有很大影響，選擇近似共線的錨節(jié)點(diǎn)組合會(huì)導(dǎo)致較大的定位誤差，而選擇集中分布的錨節(jié)點(diǎn)組合也會(huì)降低定位精度。因此，采用共線度來衡量錨節(jié)點(diǎn)組合是否有效對于WSN定位算法是有意義的，但其也有明顯不足之處，本文將在后面進(jìn)行分析說明。

2 錨節(jié)點(diǎn)的優(yōu)化選擇和定位算法

在WSN部署時(shí)，應(yīng)盡可能均勻部署或選擇錨節(jié)點(diǎn)，以最大化每個(gè)錨節(jié)點(diǎn)的貢獻(xiàn)，并避免錨節(jié)點(diǎn)共線和集中分布。目前已有相關(guān)研究人員針對這一問題進(jìn)行研究并提出共線度的概念和方法[8-11]，以優(yōu)化選擇錨節(jié)點(diǎn)進(jìn)而提高算法定位精度。

2.1 共線度

文獻(xiàn)[8]中提出采用共線度來衡量選擇的錨節(jié)點(diǎn)組合是否有效，其依據(jù)是三個(gè)錨節(jié)點(diǎn)共線或近似共線時(shí)，即便是微小的測距誤差也會(huì)導(dǎo)致較大的定位誤差,這與本文第1章的實(shí)驗(yàn)結(jié)論相同。文獻(xiàn)[8]提出了一種基于三角形最小高的“共線度”的定義(本文將其簡記為DC-H)，如圖5所示，由三個(gè)錨節(jié)點(diǎn)A、B、C構(gòu)成的三角形中三個(gè)高的最小值，即最大內(nèi)角或最長邊對應(yīng)的高的長度為這組錨節(jié)點(diǎn)的共線度：

(1)

圖5 基于最小高的錨節(jié)點(diǎn)共線度示意圖

文獻(xiàn)[9]則認(rèn)為以三角形內(nèi)角來表示共線度更為恰當(dāng)，并提出一種新的共線度定義，即三個(gè)錨節(jié)點(diǎn)所組成的三角形的內(nèi)角的余弦值的最大值(對應(yīng)三角形的最小內(nèi)角)，如圖6所示，從而得到基于最小角的共線度(本文將其簡記為DC-A)定義：

DCDC-A=max(cos(∠A),cos(∠B),cos(∠C))

(2)

由三角形余弦定理可知，△ABC的三個(gè)角的余弦值分別為：

(3)

由于三角形最小內(nèi)角的角度范圍為0～60°，則DCDC-A的取值范圍為[0.5,1]，并與角度成反比。在選擇定位錨節(jié)點(diǎn)組合時(shí)，該算法認(rèn)為DCDC-A的取值越小越好。

圖6 基于最小角的錨節(jié)點(diǎn)共線度示意圖

基于共線度的算法認(rèn)為錨節(jié)點(diǎn)以等邊三角形的形式分布最均勻，定位結(jié)果最佳,利用共線度來度量錨節(jié)點(diǎn)共線的程度，有利于選擇定位結(jié)果較好的錨節(jié)點(diǎn)組合。然而，目前尚無研究對這兩種基于不同共線度定義的定位算法進(jìn)行對比研究和分析。

2.2 基于聚集共線度和節(jié)點(diǎn)度的算法

筆者經(jīng)過分析和實(shí)驗(yàn)認(rèn)為以上兩種共線度：DC-H和DC-A的定義均有不足之處，用于WSN定位均有其局限性。文獻(xiàn)[8]中基于三角形最小高度的共線度定義只能對大小相似的三角形進(jìn)行比較，無法真正衡量不同錨節(jié)點(diǎn)組合的共線度。如圖7(a)所示，左邊△A1B1C1中的最小高h(yuǎn)1雖然比右邊△A2B2C2最小高h(yuǎn)2要小，然而△A1B1C1是鈍角三角形，其DC值要比△A2B2C2大，即DC(△A1B1C1)>DC(△A2B2C2)，即最小高越大共線度越大的假設(shè)在此并不成立；而文獻(xiàn)[9]提出的基于最小角余弦值的共線度定義可用于衡量并解決錨節(jié)點(diǎn)共線的問題，但卻無法度量錨節(jié)點(diǎn)是否集中分布，如圖7(b)所示，△D1E1F1和△D2E2F2的大小、集中程度不同，但共線度卻相同,即DC(△D1E1F1)=DC(△D2E2F2)。

圖7 DC-H和DC-A定義的缺點(diǎn)示意分析

綜合最小高和最小角兩種不同定義的共線度的優(yōu)點(diǎn)，本文提出一種新的聚集-共線度(DegreeofAggregationandCollinearity，DAC)概念。如圖8所示，在錨節(jié)點(diǎn)A、B、C組成的△ABC中，假設(shè)其中的∠A為最小內(nèi)角，h為最小高，則可綜合最小角和最小高共同衡量錨節(jié)點(diǎn)的集中和共線程度，得到的聚集-共線度DAC可表示為：

DCDAC=h/cos(∠A)

(4)

DCDAC由最小高的值和最小角對應(yīng)的余弦值共同決定，其與最小高的大小成正比，與最小角的余弦值成反比。DCDAC越大，表明共線程度或聚集程度越小，反之亦然。結(jié)合前面基于最小角度和最小高度這兩種共線度的定義，其表達(dá)式亦可表示為：

(5)

圖8 錨節(jié)點(diǎn)的聚集-共線度

除了錨節(jié)點(diǎn)的共線度會(huì)對定位結(jié)果產(chǎn)生較大影響之外，錨節(jié)點(diǎn)與其他節(jié)點(diǎn)的連通度對定位算法也有較大影響。這是因?yàn)殡x錨節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)在測算其間距或位置時(shí)會(huì)產(chǎn)生累積誤差，從而降低定位精度，如MDS-MAP算法中采用最短路徑替代節(jié)點(diǎn)間距離，基于三邊定位的算法中也存在用已定位節(jié)點(diǎn)迭代計(jì)算未知節(jié)點(diǎn)坐標(biāo)而導(dǎo)致誤差積累的問題。錨節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，實(shí)際可測得的數(shù)據(jù)就更多、更準(zhǔn)確，對算法定位結(jié)果的貢獻(xiàn)越大，由此產(chǎn)生的累積計(jì)算誤差就越小。本文借用圖論中的節(jié)點(diǎn)度(NodeDegree，ND)的概念來表示錨節(jié)點(diǎn)的連通度，即與該錨節(jié)點(diǎn)相鄰的節(jié)點(diǎn)個(gè)數(shù)。

基于以上分析和定義，本文提出一種基于聚集-共線度(DAC)和節(jié)點(diǎn)度(ND)的錨節(jié)點(diǎn)選擇算法，稱之為DAC-ND，結(jié)合錨節(jié)點(diǎn)組合的“聚集-共線度”和錨節(jié)點(diǎn)組合的“節(jié)點(diǎn)度”來綜合判斷所選的錨節(jié)點(diǎn)組合是否適用于定位，其算法表達(dá)式如式(6)所示：

DCDAC-ND=

(6)

DCDAC-ND越小，表明錨節(jié)點(diǎn)的聚集-共線度高或者連通度差，所選錨節(jié)點(diǎn)組合不適合用于定位；DCDAC-ND越大，表示共線程度和聚集程度低，錨節(jié)點(diǎn)布均勻，連通度高，更適合用于定位。

3 仿真實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證DAC-ND算法的有效性，基于測距的MDS定位算法MDS-MAP來進(jìn)行實(shí)驗(yàn)。在100m×100m的二維仿真場景中隨機(jī)部署N個(gè)節(jié)點(diǎn)，從中按照不同的算法選擇3個(gè)作為錨節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)定位。實(shí)驗(yàn)通過隨機(jī)選擇(Random)、基于最小高的共線度(DC-H)、基于最小角的共線度(DC-A)和本文提出的DAC-ND等四種算法進(jìn)行對比，節(jié)點(diǎn)通信和測距范圍為R，假設(shè)在測距范圍內(nèi)的節(jié)點(diǎn)之間距離均可測得，并分別在無測距誤差和有測距誤差兩種情況下進(jìn)行仿真實(shí)驗(yàn)。

3.1 無測距誤差條件下的實(shí)驗(yàn)結(jié)果

首先在假設(shè)無測距誤差的理想情況下，不考慮測距誤差的影響，直接對比以上四種算法的定位性能。實(shí)驗(yàn)分別以節(jié)點(diǎn)數(shù)量和測距半徑為變量，以平均定位誤差為對比參量。仿真結(jié)果如圖9所示。

圖9(a)給出了在不同節(jié)點(diǎn)數(shù)量情況下幾種算法的平均定位誤差對比曲線。節(jié)點(diǎn)測距半徑R為40 m，節(jié)點(diǎn)數(shù)量N從20增加到60，由于節(jié)點(diǎn)平均連通度增加，各算法的平均定位誤差均隨節(jié)點(diǎn)數(shù)量增加而降低。其中Random的平均定位誤差最大，DC-H與DC-A的定位誤差大小居中，而DAC-ND誤差最小、性能最好。其中DC-H算法在節(jié)點(diǎn)數(shù)量為20時(shí)要優(yōu)于DC-A，而當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，DC-A算法要優(yōu)于DC-H，說明二者互有優(yōu)劣。綜合計(jì)算可知，DAC-ND比前三種算法的誤差平均分別降低56.9%、22.6%和18.9%。

圖9(b)表示不同測距范圍情況下四種算法的平均定位誤差對比。節(jié)點(diǎn)數(shù)量N為40，測距范圍R從30 m增加到70 m，各算法的定位誤差隨測距范圍增加而下降?？擅黠@得出Random算法定位誤差最大，DC-H其次，DC-A誤差較小，DAC-ND的平均定位誤差最小。計(jì)算可得DAC-ND算法的平均定位誤差比Random、DC-H、DC-A三種算法分別降低了54.7%、23.3%和12.8%。

圖9 無測距誤差時(shí)定位算法在不同參數(shù)變量下的平均定位誤差比較

3.2 有測距誤差條件下的實(shí)驗(yàn)結(jié)果

在有測距誤差的情況下，采用乘性正態(tài)噪聲測距誤差模型，即假設(shè)節(jié)點(diǎn)間測距結(jié)果dij符合乘性正態(tài)噪聲模型[14]：

(7)

圖10 有測距誤差情況下定位算法在不同參數(shù)變量下的平均定位誤差比較

4 結(jié)語

定位技術(shù)是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)研究問題之一，在戰(zhàn)場應(yīng)用中提供了十分重要的位置信息和決策依據(jù)?，F(xiàn)有基于測距的多維定標(biāo)定位技術(shù)一方面依賴測距精度，另一方面跟算法的性能和網(wǎng)絡(luò)部署有關(guān)。本文重點(diǎn)對錨節(jié)點(diǎn)分布與定位精度之間的關(guān)系進(jìn)行研究，分析錨節(jié)點(diǎn)的分布對定位算法精度的影響，對現(xiàn)有的兩種基于共線度的錨節(jié)點(diǎn)選擇策略進(jìn)行分析，進(jìn)而提出一種基于“聚集-共線度”和“節(jié)點(diǎn)度”的錨節(jié)點(diǎn)選擇方法DAC-ND。將DAC-ND與Random隨機(jī)選擇算法、基于最小高的共線度算法DC-H和基于最小角的共線度算法DC-A等通過多個(gè)角度進(jìn)行仿真實(shí)驗(yàn)對比。結(jié)果表明，與Random相比，DC-H、DC-A和DAC-ND算法均能大幅度降低定位誤差，其中DC-H和DC-A算法的定位性能相近，而DAC-ND算法定位性能則更為優(yōu)越，從而驗(yàn)證了本文提出方法的有效性，它能夠彌補(bǔ)現(xiàn)有基于共線度定位算法的不足，進(jìn)一步提高定位精度。下一步研究可考慮通過改進(jìn)算法測距和定位誤差累積以進(jìn)一步降低定位誤差。

References)

[1] 賁偉,吳振峰,秦晅.RSSI/TDOA/DV-Distance組合定位算法[J].指揮信息系統(tǒng)與技術(shù),2012,4(3):55-59.(BEN W, WU Z F, QIN X.RSSI/TDOA/DV-Distance combined positioning algorithm [J].Command Information System and Technology, 2012, 4(3): 55-59.)

[2] 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5):857-868.(WANG F B, SHI L, REN F Y.Self-localization systems and algorithms for wireless sensor networks [J].Journal of Software, 2005, 16(5):857-868.)

[3] SHANG Y, RUML W, ZHANG Y.Localization from connectivity in sensor networks [J].IEEE Transactions on Parallel and Distributed Systems, 2004, 15(11): 961-973.

[4] LI B, HE Y G, et al.A novel localization algorithm based on isomap and partial least squares for wireless sensor networks [J].IEEE Transactions on Instrumentation and Measurement, 2013, 62(2): 304-314.

[5] WANG C Q, CHEN J M, SUN Y X, et al.Wireless sensor networks localization with isomap [C]// ICC 2009: Proceedings of the 2009 IEEE International Conference on Communications.Piscataway, NJ: IEEE, 2009: 1-5.

[6] HUANG L, WANG F B, MA C, et al.The analysis of anchor placement for self-localization algorithm in wireless sensor networks [C]// Advances in Wireless Sensor Networks, Communications in Computer and Information Science 334.Berlin: Springer, 2013: 117-126.

[7] HANEN A, FEDERICO V, ALESSANDRO P, et al.An improved anchor selection strategy for wireless localization of WSN nodes [C]// ISCC 2016: Proceedings of the 2016 IEEE Symposium on Computers and Communication.Washington, DC: IEEE Computer Society, 2016: 108-113.

[8] POGGI C, MAZZINI G.Collinearity for sensor network localization [C]// Proceedings of 2003 IEEE 58th Vehicular Technology Conference.Piscataway, NJ: IEEE, 2004: 3040-3045.

[9] 吳凌飛,孟慶虎,梁華為.一種基于共線度的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22(5):722-727.(WU L F, MENG Q H, LIANG H W.A collinearity-based localization algorithm for wireless sensor networks [J].Chinese Journal of Sensors and Actuators, 2009, 22(5):722-727.)

[10] 劉克中，崔永強(qiáng)，張金奮，等.基于Monte Carlo的多能量級移動(dòng)節(jié)點(diǎn)定位算法研究[J].計(jì)算機(jī)科學(xué),2011,38(12):61-64.(LIU K Z, CUI Y Q, ZHANG J F, et al.Improved Monte Carlo node localization scheme by using multi-energy-level beacon [J].Computer Science, 2011, 38(12):61-64.)

[11] 吳世通，陳良，李云飛,等.基于RSSI等級的蒙特卡羅定位算法應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(17):114-119.(WU S T, CHEN L, LI Y F, et al.Application and research on Monte Carlo localization algorithm based on RSSI rank [J].Computer Engineering and Applications, 2014, 50(17):114-119.)

[12] ZHANG Y Z, XIANG S, FU W Y, et al.Improved normalized collinearity DV-Hop algorithm for node localization in wireless sensor network [J].International Journal of Distributed Sensor Networks, 2014, 2014(11): 1-14.

[13] YAN X Y, SONG A G, YU J M, et al.Toward collinearity-avoidable localization for wireless sensor network [J].Journal of Sensors, 2015, 2015(2): 1-16.

[14] LATSOUDAS G and SIDIROPOULOS N D.A fast and effective multi dimensional scaling approach for node localization in wireless sensor networks [J].IEEE Transactions on Signal Processing, 2007, 55(10): 5121-5127.

HUANG Liang, born in 1985, Ph.D., engineer.His research interests include wireless sensor network, Ad Hoc network, robot network.

Improved wireless sensor network localization algorithm based on aggregation, collinearity and connectivity of anchor nodes

HUANG Liang*

(The28thResearchInstitute,ChinaElectronicsTechnologyGroupCorporation,NanjingJiangsu210007,China)

To improve the positioning accuracy of Wireless Sensor Network (WSN), the relationship between the positioning accuracy and the distribution of anchor nodes was studied, and a new anchor node selection algorithm based on the Degree of Aggregation-Collinearity (DAC) and Node Degree (ND) of anchors was proposed, namely DAC-ND.Firstly, the experimental analysis showed that the anchor nodes in collinear or concentrated distribution have a large influence on positioning accuracy.Secondly, by analyzing and comparing the anchor node selection algorithms based on Degree of Collinearity (DC), it was found that two kind of anchor node selection algorithms based on the minimum angle (DC-A) or minimum height (DC-H) have some disadvantages.Finally, combining the advantages of the above both algorithms, the new concept of DAC was proposed, and the DAC-ND algorithm was put forward based on DAC and ND.The Matlab simulation results illustrated that, the average position error of DAC-ND can be greatly reduced by 54%-73% compared with the random selection algorithm, and it also can be reduced by 15%-23% and 12%-23% compared with the anchor selection algorithms based on DC-A and DC-H respectively.The experimental results demonstrate that the DAC-ND algorithm can obtain much higher positioning accuracy compared with algorithms based on DC-A or DC-H, which proves the effectiveness of the DAC-ND algorithm.

Wireless Sensor Network (WSN); localization; anchor node; Degree of Collinearity (DC); Node Degree (ND)

2016- 06- 17;

2016- 08- 14。

黃亮(1985—)，男，湖北孝感人，工程師，博士，主要研究方向：傳感器網(wǎng)絡(luò)、Ad Hoc網(wǎng)絡(luò)、機(jī)器人網(wǎng)絡(luò)。

1001- 9081(2017)02- 0427- 05

10.11772/j.issn.1001- 9081.2017.02.0427

TP212.9; TN929.5

A