劉　偉，董恩清，宋　洋

(山東大學(xué)(威海)機電與信息工程學(xué)院，山東威海264209)

?

無線傳感器網(wǎng)絡(luò)節(jié)點三維定位的翻轉(zhuǎn)模糊檢測

劉偉，董恩清，宋洋

(山東大學(xué)(威海)機電與信息工程學(xué)院，山東威海264209)

摘要:為了解決基于測距的無線傳感器網(wǎng)絡(luò)節(jié)點三維定位中可能會發(fā)生翻轉(zhuǎn)模糊的問題，本文提出并證明了節(jié)點三維定位的翻轉(zhuǎn)模糊檢測問題，可以等價為判斷是否存在一個平面和所有參考節(jié)點的測距誤差球都相交的問題(Existence of Intersecting Plane，EIP)．為了求解EIP問題，本文進一步提出了公切面法(Common Tangent Plane，CTP)和正交投影法(Orthogonal Projection，OP)兩種求解方法．CTP方法采用的是邊界檢測原理，OP方法則將EIP問題轉(zhuǎn)化為一個角度計算問題，并用坐標(biāo)變換的方式來求解．經(jīng)過理論分析和大量的仿真證明，CTP方法雖然具有較好的檢測效果，但是計算復(fù)雜度太大;而OP方法在幾乎獲得與CTP方法相同的檢測結(jié)果的情況下，能夠大大降低求解EIP問題的計算復(fù)雜度．

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);節(jié)點三維定位;翻轉(zhuǎn)模糊;公切面;正交投影

1　引言

節(jié)點定位技術(shù)［1～5］是無線傳感器網(wǎng)絡(luò)實際應(yīng)用的重要支撐技術(shù)之一．無線傳感器網(wǎng)絡(luò)節(jié)點的定位過程就是未知節(jié)點通過與錨節(jié)點(事先已知自身位置的節(jié)點)或已經(jīng)完成定位的未知節(jié)點通信，獲得相關(guān)信息并采用一定的定位方法求出自身位置的過程．根據(jù)是否依靠測量距離，節(jié)點定位方法可以劃分為基于測距和無需測距的兩種方法［6］．其中基于測距的方法，由于定位精度高在無線傳感器網(wǎng)絡(luò)節(jié)點定位中被廣泛采用．不過基于測距的方法在定位過程中可能產(chǎn)生節(jié)點的翻轉(zhuǎn)模糊［7～10］，并且，如果定位過程中發(fā)生翻轉(zhuǎn)模糊，就可能引起節(jié)點定位的雪崩效應(yīng)，導(dǎo)致整個網(wǎng)絡(luò)節(jié)點的定位失效．因此，有必要采取一定的措施去判斷節(jié)點翻轉(zhuǎn)模糊［11，12］是否會發(fā)生，從而減小其對整個網(wǎng)絡(luò)節(jié)點定位過程的影響．

依據(jù)信息處理的實現(xiàn)方式，無線傳感器網(wǎng)絡(luò)節(jié)點定位方法可以劃分為集中式和分布式兩種方法．集中式方法需要中心節(jié)點的參與，其擴展性能不好，而分布式方法只需在未知節(jié)點自身處完成定位過程，擴展性能好．因此，相對于集中式方法，分布式方法被廣泛地應(yīng)用在無線傳感器網(wǎng)絡(luò)節(jié)點定位中［13］．而本文提出的翻轉(zhuǎn)模糊檢測方法也主要適用于分布式的定位方法．

目前，針對無線傳感器網(wǎng)絡(luò)節(jié)點定位中翻轉(zhuǎn)模糊檢測的研究都是集中在二維空間．在二維空間中主要采用魯棒四邊形的方法來檢測節(jié)點的翻轉(zhuǎn)模糊［14，15］．魯棒四邊形的方法通過判斷未知節(jié)點和三個參考節(jié)點(包括鄰居錨節(jié)點和已完成定位的鄰居節(jié)點)組成的一個四邊形是否滿足一定的幾何條件(魯棒性條件)，來確定未知節(jié)點的定位是否會發(fā)生翻轉(zhuǎn)模糊．文獻［16］對上述的四邊形進行幾何分析，量化其滿足魯棒性條件的概率分布．在實際定位中，由于未知節(jié)點到參考節(jié)點的三個測量距離均存在誤差，而文獻［14～16］中的魯棒四邊形方法在理論分析時僅假設(shè)其中的一個測距有誤差，而另外兩個測距是精確的，這是不符合實際情況的．為此文獻［17］對三個測距均有誤差的情況進行了理論分析，并提出了一種改進算法．文獻［18］則通過增加一個參考節(jié)點的方式來組成四個四邊形，然后采用文獻［17］中的方法判斷這四個四邊形的魯棒性，只有當(dāng)這些四邊形全部滿足魯棒性條件才能認(rèn)為未知節(jié)點在定位時不會發(fā)生翻轉(zhuǎn)模糊．

在二維空間中，判斷節(jié)點翻轉(zhuǎn)模糊的魯棒四邊形方法一般只適用于采用三個參考節(jié)點的三邊定位．相對于三邊定位方法，在節(jié)點的二維定位中使用多于三個參考節(jié)點的多邊定位方法更能得到較小的平均定位誤差，因此在基于測距的無線傳感器網(wǎng)絡(luò)的節(jié)點定位中，大多采用多邊定位方法．目前針對二維空間多邊定位方法中節(jié)點翻轉(zhuǎn)模糊問題研究的還是非常少，雖然文獻［17］首次提出了一種適合于多邊定位的魯棒四邊形方法，但是其計算復(fù)雜度不僅太大，而且判斷效果較差．文獻［19］將節(jié)點二維定位中的翻轉(zhuǎn)模糊問題等價為判斷是否存在一條直線和若干圓(以參考節(jié)點為圓心，以參考節(jié)點到未知節(jié)點的測距誤差絕對值的最大值為半徑)都相交(Existence of Intersecting Line，EIL)問題，并取得了較好的檢測效果．

目前，在二維空間中，對于檢測出在定位中有可能發(fā)生翻轉(zhuǎn)模糊的未知節(jié)點，大多數(shù)采用的是悲觀的處理方式，即直接不對該未知節(jié)點進行定位，從而防止其影響后續(xù)未知節(jié)點的定位精度［8，10，16～19］．這種處理方式雖然提高了節(jié)點的定位精度，但是也會降低節(jié)點的定位數(shù)量，這在某些實際應(yīng)用中是不可接受的．為此，研究者們提出了一些樂觀的處理方式．文獻［20］提出了一種魯棒半正定方法用來處理翻轉(zhuǎn)模糊的節(jié)點．文獻［21］使用的是一種二階段的模擬退火方法．文獻［22］提出了一種OFA(Optimistic localization scheme with Flip Avoidance)方法，該方法利用計算出的兩個節(jié)點位置(真實點位置和節(jié)點翻轉(zhuǎn)模糊位置)與其他鄰居節(jié)點的相互通信關(guān)系來消除翻轉(zhuǎn)模糊節(jié)點．文獻［23］則提出了一種距離沖突方法用于處理節(jié)點的翻轉(zhuǎn)模糊．

據(jù)我們所知，至今為止還沒有學(xué)者專門對無線傳感器網(wǎng)絡(luò)節(jié)點三維定位的翻轉(zhuǎn)模糊檢測方法和處理方法進行研究．而在實際應(yīng)用中，傳感器節(jié)點往往分布在三維空間內(nèi)，需要得到節(jié)點的三維空間信息，如海洋、山地、森林及各種空間飛行器等．由于計算復(fù)雜度等原因，如將目前大多數(shù)二維定位中的檢測和處理翻轉(zhuǎn)模糊的方法簡單地擴展到三維是不合適的，因此非常有必要研究三維節(jié)點定位的翻轉(zhuǎn)模糊檢測和處理方法．

在本文中，我們只是針對無線傳感器網(wǎng)絡(luò)節(jié)點三維定位中的翻轉(zhuǎn)模糊檢測問題進行討論，至于無線傳感器網(wǎng)絡(luò)節(jié)點三維定位的翻轉(zhuǎn)模糊處理問題將是我們下一步研究的方向．借鑒文獻［19］的思想，我們提出并證明了無線傳感器網(wǎng)絡(luò)節(jié)點的三維定位翻轉(zhuǎn)模糊檢測問題可以等價為判斷是否存在一個平面和若干球(以參考節(jié)點為球心，以參考節(jié)點到未知節(jié)點的測距誤差絕對值的最大值為半徑)都相交(Existence of Intersecting Plane，EIP)問題．為了求解EIP問題，本文提出了公切面法(Common Tangent Plane，CTP)和正交投影法(Orthogonal Projection，OP)兩種求解方法．

2　三維定位中節(jié)點的翻轉(zhuǎn)模糊問題

無線傳感器網(wǎng)絡(luò)節(jié)點三維定位中的翻轉(zhuǎn)模糊問題指的是當(dāng)參考節(jié)點間的位置幾乎共面時，由于測距誤差的存在，導(dǎo)致未知節(jié)點的定位存在兩個關(guān)于某一個平面成鏡像關(guān)系的估計位置．在三維空間中無線傳感器網(wǎng)絡(luò)的節(jié)點定位至少需要四個不共面的參考節(jié)點．圖1中節(jié)點A、B、C和D是位置已知的四個參考節(jié)點．其中A、B和C三點確定了一個平面m分別是它們到未知節(jié)點的測量距離．根據(jù)上述A、B、C三點和三個測距，我們可以求得未知節(jié)點可能所在的兩個位置E和E'，它們是以A、B和C為球心，分別以為半徑的三個球的交點，且E和E'關(guān)于平面m成鏡像關(guān)系．O是直線EE'與平面m的交點．假設(shè)未知節(jié)點的正確位置為E，D到E和E'兩點的距離分別為dde和d'de．D點到未知節(jié)點的測量距離用來選擇未知節(jié)點的估計位置，其選擇的標(biāo)準(zhǔn)是更接近dde(選擇E)還是更接近d'de(選擇E')．當(dāng)A、B、C、D四點幾乎共面時，dde和d'de相差不大．由于測距誤差的存在，就有可能錯誤地選擇E'作為未知節(jié)點E的估計位置．如果做出錯誤的選擇，且讓這種錯誤定位的未知節(jié)點參與其它未知節(jié)點的定位，可能導(dǎo)致整個網(wǎng)絡(luò)節(jié)點的定位失效．

3　EIP問題的提出

借鑒文獻［19］的思想，我們下面提出并證明了無線傳感器網(wǎng)絡(luò)節(jié)點的三維定位翻轉(zhuǎn)模糊檢測問題可以等價為判斷是否存在一個平面和若干球(以參考節(jié)點為球心，以參考節(jié)點到未知節(jié)點的測距誤差絕對值的最大值為半徑)都相交(EIP)的問題．

無線傳感器網(wǎng)絡(luò)節(jié)點三維定位中的多邊定位方法需用k(k≥4)個參考節(jié)點來定位一個未知節(jié)點．已知數(shù)據(jù)可以用一個集合表示，其中，pi表示第i個參考節(jié)點的位置，表示第i個參考節(jié)點到未知節(jié)點的測量距離，其中di和εi分別表示第i個參考節(jié)點到未知節(jié)點的真實距離和測距誤差．如圖2所示將每個參考節(jié)點沿著各自的測距方向平移εi至一個新的位置，可以得到另一個集合M'．與集合M不同，集合M'沒有測距誤差．因此，在集合M'中，如果平移后的k個位置不共面，那么，在未知節(jié)點定位過程中肯定不會發(fā)生翻轉(zhuǎn)模糊．

在實際情況下，測距誤差εi是未知的，所以無法求出參考節(jié)點平移后的位置．不過εi的取值是有界限的，故可以估計所處的區(qū)域范圍．若δi表示未知節(jié)點到第i個參考節(jié)點測距誤差絕對值的最大值，即δi= max|εi|，i =1，2，…，k．那么，如圖2所示必然在以pi為球心，δi為半徑的球內(nèi)．可以用集合S ={〈pi，δi〉}，i =1，2，…，k表示這k個球．對于集合S，若存在一個平面和k個球都相交，那么pi平移后的位置珓pi有可能共面，則會發(fā)生節(jié)點的翻轉(zhuǎn)模糊;否則，珓pi肯定不會共面，也不會發(fā)生翻轉(zhuǎn)模糊．所以，翻轉(zhuǎn)模糊問題可以等價為判斷是否存在一個平面和若干球都相交(EIP)問題．

3.1三維定位中檢測翻轉(zhuǎn)模糊的CTP方法

借鑒文獻［19］在二維空間中使用CT(Common Tangent)方法求解EIL問題的思想，這里我們將CT方法擴展為適合在三維空間中求解EIP問題的CTP方法．該方法采用邊界檢測的方式來求解EIP問題．其理論基礎(chǔ)來自于我們提出的定理1．

定理1給定一個球的集合S ={〈pi，δi〉}，i =1，2，…，k．EIP問題的充要條件是在集合S中存在三個球的一個公切面，該公切面與其余的球都相交．

證明定理1的必要性是顯而易見的，因此，只需對其充分性進行證明．

我們用一個集合N(S)表示與集合S中所有的球都相交的平面．這樣EIP問題實際上就是判斷集合N(S)是否為空集．如圖3(a)所示，當(dāng)N(S)不為空集時，N(S)中的一個邊界平面n1(將要偏離和所有球都相交條件的平面)必然與其中的一個球(圖3中為球A)相切，而與其余的球都相交．

我們將平面n1圍繞球A的球心旋轉(zhuǎn)(保證在旋轉(zhuǎn)的過程中平面與球A一直相切)，在旋轉(zhuǎn)的過程中，各球與平面的交線所包圍區(qū)域的面積肯定會有所變化(增大或減小)，當(dāng)首先出現(xiàn)有某一個球(假設(shè)為球B)與平面的交線所包圍區(qū)域的面積等于0時，停止旋轉(zhuǎn)，這時我們可以得到如圖3(b)所示的平面n2，此時平面n2與球A和球B均相切，而且與集合S中除了球A和球B以外的其余球都相交．我們再將平面n2圍繞球A和球B的兩個球心的連線旋轉(zhuǎn)(保證在旋轉(zhuǎn)的過程中平面與球A、球B一直相切)，當(dāng)首先出現(xiàn)某一個球(假設(shè)為球C)與平面的交線所包圍區(qū)域的面積最先等于0時，停止旋轉(zhuǎn)，這時我們可以得到如圖3(c)所示的平面n3．平面n3就是球A、球B和球C的一個公切面，而且與集合S中除了球A、球B和球C以外的其余球都相交．定理1的充分性得到了證明．

根據(jù)定理1，我們提出了一種CTP方法求解EIP問題．CTP方法的流程圖如圖4所示．從圖4中可以看出，CTP方法對集合S中任意三個球組成的一個子集，都需要求出其公切面，然后再判斷這些公切面與其余球的相交性．求解公切面的計算復(fù)雜度為O (k3)，判斷公切面與球相交性的計算復(fù)雜度為O(k)．因此，CTP方法總的計算復(fù)雜度為O(k4)，其計算復(fù)雜度非常高．

3.2三維定位中檢測翻轉(zhuǎn)模糊的OP方法

由于CTP方法的計算復(fù)雜度太高，為了降低求解EIP問題的計算復(fù)雜度，我們下面提出了一種計算復(fù)雜度較低的OP方法．

3．2．1基本定義及基本定理

在詳細(xì)介紹OP方法之前，我們需要給出和證明如下一個基本定義和兩個基本定理．

下面給出的基本定義是有關(guān)三維空間中球到直線的正交投影的概念．

定義假設(shè)三維空間中存在一個球和一條直線，那么這個球有一條直徑必然和該直線平行．從這條直徑的兩個端點分別向該直線做垂線．兩個垂足之間的線段稱為球在該直線上的正交投影線段．

如圖5所示，根據(jù)上面的定義，線段AB就是球O在直線l上的正交投影線段，且其長度等于該球的直徑．

根據(jù)上面的定義，我們給出如下基本定理及其證明．

定理2假設(shè)在三維空間中存在一條直線和經(jīng)過該直線的任意一個平面，那么可得到球在該平面上的正交投影圓，這個正交投影圓在該直線上的正交投影線段與球在該直線上的正交投影線段是等價的．

證明如圖6所示，三維空間中有一個球O和一條直線l，直線l在平面p內(nèi)．線段AB是球O的直徑，且AB∥l．圓O'是球O在平面p上正交投影所得到的圓．線段CD是線段AB在平面p上的正交投影線段．

若線段MN為圓O'在直線l上的正交投影線段．那么MN⊥CM．因為線段CD是線段AB在平面p上的正交投影線段，所以線段AC垂直于平面p，即MN⊥AC．因此，MN垂直于平面ACM．由此可以得出MN⊥AM．同理，可得出MN⊥BN，即線段MN是球O在直線l上的正交投影線段．

若線段MN為球O在直線l上的正交投影線段．那么MN⊥AM．因為線段CD是線段AB在平面p上的正交投影線段，所以線段AC垂直于平面p，即MN⊥AC．因此，MN垂直于平面ACM．由此可以得出MN⊥CM．同理，可得出MN⊥DN，即線段MN是圓O'在直線l上的正交投影線段．

下面的基本定理是文獻［24］中給出的一條定理，該定理給出了二維空間中存在與所有圓都相交的直線的充要條件．

定理3在二維空間中給定一個圓的集合Q ={〈pi，δi〉}，i =1，2，…，k．其中pi表示圓心，δi表示圓的半徑，k表示圓的個數(shù)．二維空間中存在一條直線與集合Q中所有的圓都相交的充要條件是空間中存在一條直線，使集合Q中的任意兩個圓在該直線上的正交投影線段有重疊部分．

3．2．2 OP方法的理論基礎(chǔ)

OP方法的理論基礎(chǔ)來自于下面提出并證明的定理4．該定理巧妙地給出了EIP問題的一個充要條件．

定理4給定一個球的集合S ={〈pi，δi〉}，i =1，2，…，k．EIP問題的充要條件是三維空間中存在一條直線，集合S中任意兩個球在該直線上的正交投影線段有重疊部分．

證明

(1)必要性證明

如圖7所示，假設(shè)三維空間中存在k個球G1，G2，…，Gk和一條直線l，其中任意兩個球在直線l上的正交投影線段有重疊部分．

任取一個經(jīng)過直線l的平面P，從而可以得到這k個球在平面P上的正交投影圓O1，O2，…，Ok．由于任意兩個球在直線l上的正交投影線段有重疊部分，根據(jù)定理2的等價原理，平面P上的這k個圓中的任意兩個圓在直線l上的正交投影線段有重疊部分．由定理3可知，在平面P上必然有一條直線m和這k個圓都相交．過直線m作一個平面Q，使Q⊥P．那么，平面Q必然和這k個球都相交．

(2)充分性證明

從另一個角度看圖7，假設(shè)三維空間中存在k個球G1，G2，…，Gk和一個平面Q，平面Q和這k個球都相交．

作平面Q的任意一個垂直平面P，從而得到k個球在平面P上的正交投影圓O1，O2，…，Ok和平面Q在平面P上的正交投影直線m．由于平面Q和k個球都相交，所以在平面P上，直線m必然和k個正交投影圓均相交．根據(jù)定理3，在平面P上必然有一條直線l，使得這k個圓中的任意兩個圓在直線l上的正交投影線段有重疊部分．由定理2的等價原理可知，k個球中的任意兩個球在直線l上的正交投影線段有重疊部分．

3．2．3 OP方法的計算過程

根據(jù)定理4，我們提出了一種求解EIP問題的OP方法．OP方法的核心就是在三維空間中尋找滿足條件的直線．根據(jù)正交投影的性質(zhì)，對于一系列相互平行的直線來說，EIP問題中的k個球在這些直線上的正交投影線段的相交性是完全一致的．因此OP方法實際是尋找直線的方向向量．不失一般性，我們假設(shè)尋找的直線經(jīng)過坐標(biāo)原點．我們提出的OP方法把尋找直線方向向量的問題轉(zhuǎn)化為了角度計算問題，轉(zhuǎn)化的理論根據(jù)是如下提出和證明的定理5．

定理5對于三維空間中的一條過坐標(biāo)原點的直線，可以得到其到兩個坐標(biāo)平面的兩條正交投影直線，已知這兩條正交投影直線與這兩個坐標(biāo)平面的共同坐標(biāo)軸正方向之間的兩個夾角，就能夠確定這條直線．

證明如圖8所示，直線l經(jīng)過坐標(biāo)原點，直線l1和l2分別是直線l到坐標(biāo)平面xOy和xOz上的正交投影，它們與x軸正方向的夾角分別為α和β．

由于直線l經(jīng)過坐標(biāo)原點，所以它到兩個坐標(biāo)平面的正交投影l(fā)1和l2也經(jīng)過坐標(biāo)原點．已知直線l1和l2與x軸正方向的夾角α和β，就可以確定這兩條直線l1和l2．我們過直線l1作坐標(biāo)平面xOy的一個垂直平面P，那么直線l在平面P內(nèi)．同理，我們過直線l2做坐標(biāo)平面xOz的一個垂直平面Q，那么直線l也在平面Q內(nèi)．所以平面P和平面Q的交線就是直線l．

根據(jù)定理5，OP方法可以轉(zhuǎn)化為尋找滿足條件的兩個夾角的問題．在EIP問題中，假設(shè)各球的球心坐標(biāo)為(xi，yi，zi)，半徑為ri，i = 1，2，…，k．若我們所尋找的直線l在坐標(biāo)平面xOy和xOz上的正交投影l(fā)1和l2與x軸正方向的夾角分別為α和β(0≤α，β＜π)．為了簡便計算，本文采用坐標(biāo)變換的方式求出各球在直線l上的正交投影線段．坐標(biāo)變換的目的是使新坐標(biāo)系的橫坐標(biāo)軸與直線l重合，需要兩步變換．

在如圖9(a)所示的原始坐標(biāo)系中，直線l1和l2分別是直線l在坐標(biāo)平面xOy和xOz上的正交投影，它們與x軸正方向的夾角分別為α和β．第1步坐標(biāo)變換將原始坐標(biāo)系Oxyz圍繞z軸旋轉(zhuǎn)角度α，得到如圖9(b)所示的坐標(biāo)系O'x'y'z'，此時，直線l位于坐標(biāo)平面x'O' z'內(nèi)，而直線l到坐標(biāo)平面x'O'y'的正交投影l(fā)1'與x'軸重合．第2步坐標(biāo)變換將坐標(biāo)系O'x'y'z'圍繞y'軸旋轉(zhuǎn)角度β，得到如圖9(c)所示的坐標(biāo)系O″x″y″z″，此時，直線l與x″軸重合．

由坐標(biāo)變換的公式，可以得出各球的球心在坐標(biāo)系O″x″y″z″上的坐標(biāo)為:

而各球心到直線l上的正交投影點在坐標(biāo)系O″x″y″z″上的坐標(biāo)為:

因此若任意兩個球在直線l上的正交投影線段有重疊部分，則必須滿足:

其中:

式(2)表示的是一個二元非線性不等式組．目前一般采用最優(yōu)化的方法對多元非線性不等式組進行求解［25～27］．采用最優(yōu)化方法求解需要對式(2)作一個變換，可以得到:

假設(shè):

式(3)可以用式(4)來表示．

我們令φl(X) = max(0，fl(X) )，那么:

由式(5)可知φl(X)0，因此最優(yōu)化方法求解該不等式組的目標(biāo)函數(shù)可以作如下的設(shè)置:

粒子群優(yōu)化方法［28］(Particle Swarm Optimization，PSO)是一種搜索性能較好的優(yōu)化方法，它具有收斂速度快、可調(diào)參數(shù)少、易于實現(xiàn)等優(yōu)點．本文采用PSO方法對式(2)中不等式組進行求解，其求解步驟如下:

①初始化各參數(shù)，包括加速常數(shù)c1和c2，最大迭代次數(shù)Tmax，粒子的速度范圍［vmin，vmax］，粒子的數(shù)目s和慣性權(quán)重的范圍［ωmin，ωmax］．

⑤分別根據(jù)式(7)、式(8)和式(9)更新慣性權(quán)重、粒子的速度和粒子的位置．

式(8)中，r1和r2為均勻分布在［0，1］區(qū)間的隨機數(shù)．在更新過程中，如果將其置為vmin，如果將其置為vmax;如果?［0，π］，則在［0，π］內(nèi)隨機生成

⑥讓迭代次數(shù)t = t + 1，然后檢驗t是否小于Tmax，若條件滿足轉(zhuǎn)入步驟④，否則，說明不等式組無解，未知節(jié)點的定位不會發(fā)生翻轉(zhuǎn)模糊．

最優(yōu)化方法的一個缺點就是在搜索過程中不可避免地會陷入到局部最優(yōu)值，無法找到全局最優(yōu)．因此對于本身有解的不等式組，用最優(yōu)化方法求解可能會出現(xiàn)不等式組無解的情況．這樣會導(dǎo)致把有可能發(fā)生翻轉(zhuǎn)模糊的未知節(jié)點誤判為不會發(fā)生翻轉(zhuǎn)模糊．為了降低誤判率，對于檢測出在定位過程中不會發(fā)生翻轉(zhuǎn)模糊的未知節(jié)點，可以使用q(q1)次PSO方法搜索不等式組的解，只有當(dāng)這q次都搜索不到解時，才認(rèn)為未知節(jié)點的定位不會發(fā)生翻轉(zhuǎn)模糊．

OP方法的流程圖如圖10所示．從圖10中可以看出，對集合S中的每一對球，OP方法都要按照式(2)列出一個不等式，并將這些不等式合成一個不等式組，再用PSO方法進行求解．因此，OP方法總的計算復(fù)雜度僅為O(k2)．而CTP方法的計算復(fù)雜度為O(k4)，相比之下，其計算復(fù)雜度遠(yuǎn)小于CTP方法．

4　仿真分析

為了驗證CTP和OP方法的性能，我們在一臺CPU 為Intel Core i7-3770(3.40GHz)，內(nèi)存為16GB的計算機上，用Matlab R2013a軟件對其進行了仿真分析．采用的測距方法是RSSI(Received Signal Strength Indication)，其測距誤差［29］可以表示為e = d×10σ/10n，其中e表示測距誤差，d表示節(jié)點間的真實距離，n為路徑損耗指數(shù)(文中設(shè)定為4)，σ表示高斯白噪聲(文中均值為0，標(biāo)準(zhǔn)差為4)．仿真時PSO方法各參數(shù)的取值如下:

最大迭代次數(shù): Tmax= 20;粒子的數(shù)目: s = 50;粒子的速度: vmin=－1，vmax= 1;慣性權(quán)重:ωmin= 0.4，ωmax= 0.9;加速常數(shù): c1= c2=2．

4.1檢測結(jié)果的對比分析

我們在邊長為100m的正方體網(wǎng)絡(luò)區(qū)域中放置了125個節(jié)點，其中20個為錨節(jié)點．仿真的節(jié)點分布分別為均勻分布和隨機分布兩種類型，通信半徑結(jié)合節(jié)點間距確定為50m．均勻分布時，節(jié)點間距離是20m(存在0～2m的隨機誤差)．

圖11是CTP方法和OP方法(q =1)對上述網(wǎng)絡(luò)檢測結(jié)果的對比．從圖中可以看出，除了在節(jié)點隨機分布時，有一個節(jié)點的檢測結(jié)果不同(CTP方法檢測可能發(fā)生翻轉(zhuǎn)模糊，OP方法檢測不會發(fā)生翻轉(zhuǎn)模糊)以外，其余的節(jié)點檢測結(jié)果是完全相同的．導(dǎo)致OP方法與CTP方法檢測結(jié)果出現(xiàn)不同的原因是OP方法在用PSO方法求解不等式組時，PSO方法在搜索過程中陷入到局部最優(yōu)值，從而錯誤得出了不等式組無解的結(jié)論．實際上從第3節(jié)可以看出，OP方法和CTP方法的基本原理是一致的，而且從圖11中可以看出，兩種檢測方法檢測結(jié)果不一致的比例(OP方法的誤判率)非常的?。?/p>

為了測試OP方法的誤判率，我們對上述網(wǎng)絡(luò)進行了100次的仿真．表1和表2分別是節(jié)點均勻分布和隨機分布時TCP方法和OP方法對網(wǎng)絡(luò)進行100次檢測結(jié)果的對比情況．對于未知節(jié)點的檢測，我們用0表示可能發(fā)生翻轉(zhuǎn)模糊，用1表示不會發(fā)生翻轉(zhuǎn)模糊．表1和表2中q表示OP方法中求解不等式組時使用PSO方法的次數(shù); N1表示CTP方法和OP方法檢測結(jié)果均為0的未知節(jié)點的數(shù)目; N2表示CTP方法檢測結(jié)果為0，OP方法檢測結(jié)果為1的未知節(jié)點的數(shù)目; N3表示CTP方法檢測結(jié)果為1，OP方法檢測結(jié)果為0的未知節(jié)點的數(shù)目; N4表示CTP方法和OP方法檢測結(jié)果均為1的未知節(jié)點的數(shù)目; N5表示由于參考節(jié)點小于4個，而無法定位的未知節(jié)點的數(shù)目; P表示OP方法的誤判率，即:

表1　節(jié)點均勻分布檢測結(jié)果對比

表2　節(jié)點隨機分布檢測結(jié)果對比

從表1和表2中可以看出，在所有情況下，N3均為0，因此CTP方法和OP方法檢測結(jié)果的不同僅體現(xiàn)在N2上，即CTP方法檢測結(jié)果為未知節(jié)點可能會發(fā)生翻轉(zhuǎn)模糊，而OP方法的檢測結(jié)果為未知節(jié)點不會發(fā)生翻轉(zhuǎn)模糊．這和我們上面的理論分析是一致的．另外，從表中還可以看出，適當(dāng)?shù)卦黾邮褂肞SO方法的次數(shù)q，可以降低誤判率．不過隨著q的增加，所需要的檢測時間也增加，當(dāng)q等于4時，誤判率已經(jīng)很低了，而且q大于4時，誤判率的降低已經(jīng)不明顯了，因此，在實際應(yīng)用中我們可以選擇q的值為4．

4.2平均定位誤差的對比分析

下面，我們在節(jié)點定位的過程中加入翻轉(zhuǎn)模糊檢測，對節(jié)點分別經(jīng)過CTP方法和OP方法定位后得到的平均定位誤差進行仿真對比分析．本文我們主要是對TCP方法和OP方法的檢測結(jié)果進行對比，所以在仿真中對檢測出的可能發(fā)生翻轉(zhuǎn)模糊節(jié)點的處理采用相對簡單的悲觀處理方式．

球的數(shù)量和各球的半徑是EIP問題中的兩個主要的變量．由于在本文的仿真環(huán)境中，節(jié)點的密度保持不變，所以此仿真環(huán)境下它們在無線傳感器網(wǎng)絡(luò)三維節(jié)點定位問題中分別等價于節(jié)點的通信半徑和單位檢測誤差．因此，為了研究這兩個變量對CTP方法和OP方法檢測結(jié)果的影響，我們分別采用不同節(jié)點通信半徑和不同的單位檢測誤差，仿真分析網(wǎng)絡(luò)的平均定位誤差的變化．文中的平均定位誤差采用如下公式計算:

式(11)中，e表示平均定位誤差，N表示仿真的網(wǎng)絡(luò)數(shù)目(本文為100個)，(xi，yi，zi)和(^xi，^yi，^zi)分別表示節(jié)點i的真實坐標(biāo)和估計坐標(biāo)，Vn表示在第n個網(wǎng)絡(luò)中能夠定位的節(jié)點的集合，|Vn|表示集合Vn中節(jié)點的數(shù)量，R表示通信半徑．本次仿真網(wǎng)絡(luò)的各參數(shù)與4.1節(jié)相同．

圖12和圖13分別表示在不同通信半徑和不同單位檢測誤差的情況下，對節(jié)點分別經(jīng)過無翻轉(zhuǎn)模糊檢測、CTP方法檢測和OP方法檢測(q分別為1和4)以后得到的平均定位誤差曲線．其中，圖12(a)和圖13 (a)為節(jié)點均勻分布，圖12(b)和圖13(b)為節(jié)點隨機分布．圖12中單位檢測誤差為0.5m，圖13中通信半徑為50m．從圖12和圖13中可以看出，與不進行任何翻轉(zhuǎn)模糊檢測相比，加入翻轉(zhuǎn)模糊檢測后，由于去除了有可能發(fā)生翻轉(zhuǎn)模糊的節(jié)點引入的高定位誤差，而且避免了翻轉(zhuǎn)模糊節(jié)點對其它未知節(jié)點定位的影響，所以得到的平均定位誤差明顯更小，也就是相對提高了整體網(wǎng)絡(luò)節(jié)點的定位精度．另外，還可以看出，由于CTP方法和OP方法(q分別為1和4)的檢測結(jié)果差別不大，導(dǎo)致其得到的三條平均定位誤差曲線幾乎重合在一起．

為了更加清晰地展現(xiàn)CTP方法和OP方法(q分別為1和4)檢測結(jié)果的差別，下面我們把圖12和圖13中無翻轉(zhuǎn)模糊檢測的曲線去除，可以得到圖14和圖15所示的結(jié)果．從圖14和圖15中可以看出在兩種節(jié)點分布下，當(dāng)q =4時，OP方法和CTP方法進行翻轉(zhuǎn)模糊檢測后得到的平均定位誤差曲線幾乎是完全重合的，而當(dāng)q =1時，OP方法和CTP方法檢測得到的平均定位誤差也非常接近．這就進一步說明了OP方法和CTP方法對翻轉(zhuǎn)模糊的檢測結(jié)果相差不大，當(dāng)q =4時，兩者幾乎能夠取得相同的檢測結(jié)果．

4.3檢測時間的對比分析

為了比較CTP方法和OP方法的計算復(fù)雜度，我們對它們的檢測時間進行了仿真，仿真采用4.2節(jié)中不同通信半徑的網(wǎng)絡(luò)及其參數(shù)．

表3和表4分別是節(jié)點均勻分布和隨機分布時，100個不同網(wǎng)絡(luò)仿真的計算時間平均值．在表中，R和N分別表示節(jié)點的通信半徑和參考節(jié)點的平均數(shù)，TCTP表示CTP方法檢測一次所需的平均時間，TOP1表示q =1時，OP方法檢測一次所需的平均時間，TOP4表示q = 4時，OP方法檢測一次所需的平均時間，β1表示q =1時，OP方法與TCP方法所需時間的比值，即β1= TCTP/TOP1，β4表示q =4時，OP方法與TCP方法所需時間的比值，即β4= TCTP/TOP4．從表3和表4中可以看出，在兩種節(jié)點分布的情況下，隨著參考節(jié)點數(shù)目N的增加，CTP方法檢測的平均時間TCTP增加的非?？欤鳲P方法檢測的平均時間TOP1和TOP4則增加比較緩慢．另外除了通信半徑為40m時，TOP4大于TCTP之外，其余情況下，TOP1和TOP4均小于TCTP，而且隨著參考節(jié)點數(shù)量的增加，β1和β4的值越來越大，因此，當(dāng)參考節(jié)點數(shù)量較多時，OP方法明顯地更適用．這就說明了與CTP檢測方法相比，OP方法在取得了幾乎相同判斷結(jié)果的同時，大大降低了計算復(fù)雜度．

表3　節(jié)點均勻分布時間對比

表4　節(jié)點隨機分布時間對比

5　結(jié)論

節(jié)點的翻轉(zhuǎn)模糊是基于測距的無線傳感器網(wǎng)絡(luò)節(jié)點定位過程中需要解決的一個關(guān)鍵問題．針對目前對節(jié)點翻轉(zhuǎn)模糊檢測方法的研究都是集中在二維空間，缺乏對三維空間檢測方法研究的現(xiàn)狀．本文將無線傳感器網(wǎng)絡(luò)節(jié)點的三維定位翻轉(zhuǎn)模糊檢測問題等價為EIP問題，并提出了CTP和OP兩種檢測方法．CTP方法有較好的檢測效果，不過其計算復(fù)雜度太大．OP方法的檢測效果雖然不如CTP方法，但是其具有計算復(fù)雜度較低的優(yōu)點，并且OP方法的檢測結(jié)果與CTP方法的檢測結(jié)果相差很小，通過增加OP方法中使用PSO方法的次數(shù)q，兩者的差別越來越小，當(dāng)q = 4時，OP方法和CTP方法幾乎能取得相同的檢測結(jié)果．

對于樂觀的定位方法來說，檢測出有可能發(fā)生翻轉(zhuǎn)模糊的節(jié)點之后，需要采用一些方法對其進行處理．而目前對節(jié)點翻轉(zhuǎn)模糊處理方法的研究都是集中在二維空間，缺乏對三維空間處理方法的研究．由于計算復(fù)雜度等原因，如將目前大多數(shù)二維定位中處理翻轉(zhuǎn)模糊的方法簡單地擴展到三維是不合適的，因此，下一步我們將對無線傳感器網(wǎng)絡(luò)節(jié)點三維定位的翻轉(zhuǎn)模糊處理方法進行研究．

參考文獻

［1］H J Shao，X P Zhang，et al．Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables［J］．IEEE Transactions on Signal Processing，2014，62(10) : 2580－2594．

［2］J A Jiang，X Y Zheng，et al．A distributed RSS-based localization using a dynamic circle expanding mechanism［J］．IEEE Sensors Journal，2013，13(10) : 3754－3766．

［3］N Deshpande，E Grant，et al．Target Localization and autonomous navigation using wireless sensor networks-a pseudogradient algorithm approach［J］．IEEE Systems Journal，2014，8(1) : 93－103．

［4］Y Z Chai，E Q Dong．A three-dimensional localization algorithm for wireless sensor networks based on the BFGS optimization［A］．Proceedings of the 17th European Wireless Conference［C］．Vienna: VDE，2011．676－680．

［5］E Q Dong，Y Z Chai，et al．A novel three-dimensional localization algorithm for Wireless Sensor Networks based on Particle Swarm Optimization［A］．Proceedings of the 18th International Conference on Telecommunications［C］．Ayia Napa: IEEE，2011．55－60．

［6］N Salman，M Ghogho，et al．Optimized low complexity sensor node positioning in wireless sensor networks［J］．IEEE Sensors Journal，2014，14(1) : 39－46．

［7］T Eren，O K Goldenberg，et al．Rigidity，computation，and randomization in network localization［A］．Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies［C］．Hong Kong: IEEE，2004．2673－2684．

［8］J Aspnes，T Eren，et al．A theory of network localization ［J］．IEEE Transactions on Mobile Computing，2006，5 (12) : 1663－1678．

［9］R Connelly．Generic global rigidity［J］．Discrete and Computational Geometry，2005，33(4) : 549－563．

［10］A Kannan，B Fidan，et al．Use of flip ambiguity probabilities in robust sensor network localization［J］．Wireless Networks，2011，17(5) : 1157－1171．

［11］A Kannan，B Fidan，et al．Derivation of flip ambiguity probabilities to facilitate robust sensor network localization ［A］．Proceedings of Wireless Communications and Networking Conference［C］．Budapest: IEEE，2009．1－6．

［12］A Kannan，B Fidan，et al．Robust distributed sensor network localization based on analysis of flip ambiguities ［A］．Proceedings of Global Telecommunications Conference［C］．New Orleans: IEEE，2008．1－6．

［13］Q J Shi，C．He，et al．Distributed wireless sensor network localization via sequential greedy optimization algorithm ［J］．IEEE Transactions on Signal Processing，2010，58 (6) : 3328－3340．

［14］D Moore，J Leonard，et al．Robust distributed network localization with noisy range measurements［A］．Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems［C］．Baltimore: ACM，2004．50 －61．

［15］F Sittile，M Spirito．Robust localization for wireless sensor networks［A］．Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks［C］．San Francisco: IEEE，2008．46－54．

［16］A Kannan，B Fidan，et al．Analysis of flip ambiguities in distributed network localization［A］．Proceedings of Information，Decision and Control［C］．Adelaide: IEEE，2007．193－198．

［17］A Kannan，B Fidan，et al．Analysis of flip ambiguities for robust sensor network localization［J］．IEEE Transactions on Vehicular Technology，2010，59(4) : 2057－2070．

［18］D S Chen，X Y Li，et al．An improved quadrilateral localization algorithm for wireless sensor networks［A］．Proceedings of IEEE/ICME International Conference on Complex Medical Engineering［C］．Harbin: IEEE，2011．268－273．

［19］X Wang，Z Yang，et al．Beyond rigidity: obtain localizability with noisy ranging measurement［J］．International Journal of Ad Hoc and Ubiquitous Computing: special issue on Wireless Network Algorithm and Theory，2011，8 (1) : 114－124．

［20］S Severi，G Abreu，et al．Understanding and solving flipambiguity in network localization via semidefinite programming［A］．Proceedings of Global Telecommunications Conference［C］．Honolulu: IEEE，2009．1－6．

［21］A Kannan，G Q Mao，et al．Simulated annealing based wireless sensor network localization with flip ambiguity mitigation［A］．Proceedings of the 63rd IEEE Vehicular Technology Conference［C］．Melbourne: IEEE，2006．1022－1026．

［22］X P Wang，Y H Yang，et al．OFA: An optimistic approach to conquer flip ambiguity in network localization［J］．Computer Networks，2013，57(6) : 1529－1544．

［23］Q J Xiao，B Xiao，et al．Iterative localization of wireless sensor networks: an accurate and robust approach［J］．Computer Communications，2012，35(13) : 608－621．

［24］W Liu，E Q Dong，et al．An improved flip ambiguity detection algorithm in wireless sensor networks node localization［A］．Proceedings of the 21st International Conference on Telecommunications［C］．Lisbon: IEEE，2014．206－212．

［25］J B Jian，X L Zhang，et al．A new finitely convergent algorithm for systems of nonlinear inequalities［J］．Applied Mathematics Letters，2007，20(4) : 405－411．

［26］C He，C F Ma．A smoothing self-adaptive Levenberg-Marquardt algorithm for solving system of nonlinear inequalities［J］．Applied Mathematics and Computation，2010，216 (10) : 3056－3063．

［27］M Sahba．On the solution of nonlinear inequalities in a finite number of iterations［J］．Numerische Mathematik，1985，46(2) : 229－236．

［28］R V Kulkarni，G K Venayagamoorthy．Particle swarm optimization in wireless-sensor networks: a brief survey［J］．IEEE Transactions on Systems，Man，and Cybernetics，Part C: Applications and Reviews，2011，41(2) : 262－267．

［29］M Rahman，L Kleeman．Paired measurement localization: a robust approach for wireless localization［J］．IEEE Transactions on Mobile Computing，2009，8 (8) : 1087 －1102．

劉偉男，1979年出生于山東兗州．2009年于昆明理工大學(xué)獲得碩士學(xué)位，2010年起于山東大學(xué)攻讀博士學(xué)位，主要研究方向為無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)．

E-mail: lwsdjnyz@163．com

董恩清(通信作者)男，1965年出生于遼寧營口，博士，山東大學(xué)(威海)教授、博士生導(dǎo)師．2002年于西安交通大學(xué)獲信息與通信工程專業(yè)博士學(xué)位．2006年～2007年在美國哈佛大學(xué)做訪問學(xué)者．主要研究方向包括無線通信技術(shù)、無線傳感器網(wǎng)絡(luò)、醫(yī)學(xué)圖像處理等．

E-mail: enqdong@ sdu．edu．cn

Flip Ambiguity Detection for Three-Dimensional Node Localization in Wireless Sensor Networks

LIU Wei，DONG En-qing，SONG Yang
(School of Mechanical，Electrical＆Information Engineering，Shandong University，Weihai，Shandong 264209，China)

Abstract:To detect flip ambiguity for range-based three-dimensional node localization in wireless sensor networks，we have proposed and proved that flip ambiguity detection for three-dimensional node localization is equal to whether there is a plane intersecting with all range error spheres of the reference nodes，which is called the existence of intersecting plane (EIP) problem．To solve EIP problem，we further have proposed two solving algorithms: common tangent plane algorithm (CTP) and orthogonal projection algorithm (OP)．CTP adopts the principle of boundary detection，while OP transforms EIP problem into an angle calculation problem and adopts a coordinate transformation method to solve the problem．The simulation experiments demonstrate that CTP has good detection results，but its computational complexity is too high; however，OP has almost the same detection results as CTP and has lower computational complexity．

Key words:wireless sensor networks; three-dimensional node localization; flip ambiguity; common tangent plane; orthogonal projection

作者簡介

基金項目:國家自然科學(xué)基金(No．81371635) ;高等學(xué)校博士學(xué)科點專項科研基金(No．20120131110062) ;山東省科技發(fā)展計劃項目(No．2013GGX10104)

收稿日期:2014-06-26;修回日期: 2014-09-25;責(zé)任編輯:馬蘭英

DOI:電子學(xué)報URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．019

中圖分類號:TP212; TN92

文獻標(biāo)識碼:A

文章編號:0372-2112 (2016) 02-0374-11