基于模糊聚類的加權協(xié)作定位算法

汪子為，房亮

（延安大學 物理與電子信息學院,陜西延安 716000）

無線傳感器網絡被應用于許多領域，例如環(huán)境監(jiān)控，醫(yī)療機構中的患者跟蹤，軍事行動和活動區(qū)域識別[1]。在上述應用場景中，無線傳感器網絡的大多數(shù)應用都需要通過傳感器定位獲取目標的位置信息，才能更好地了解該目標地區(qū)的情況，以便及時采取有效的措施和控制[2]。但是，當無線傳感器被部署在偏遠和惡劣的環(huán)境中時，其性能則會受到資源和傳輸?shù)南拗芠3]，因此提高節(jié)點定位精度和網絡效率成為無線傳感器網絡中的主要挑戰(zhàn)。

無線傳感器網絡的定位技術一般可分為兩種：基于測距的定位技術和無需測距的定位技術[4]。其中無需測距的技術只能進行粗略定位，無法滿足高精度需求，而基于測距的技術雖然定位精度相對較高，但對軟硬件同時也有更高的要求[5]?；诮邮招盘枏姸龋≧eceived Signal Strength Indication,RSSI）的測距技術是無線傳感器網絡定位中常用的測距方法之一，網絡中每個節(jié)點之間的距離可由RSSI估算[6]。但是由于反射、多徑傳播等因素的影響，RSSI值可能會不準確，導致定位出現(xiàn)較大的誤差。為了減小RSSI測距誤差，研究人員進行了許多角度的嘗試。Shen等[7]通過使用加權質心算法將RSSI測量值加權使定位更加精準。Hussein等[8]則將梯度下降算法應用于表示RSSI測距精度的目標函數(shù)中，達到減小誤差的效果。Hongbo等[9]設計深度神經網絡作為分類器，將定位問題建模為分類問題，在利用RSSI測距時輔以信道狀態(tài)信息和基于定位的深度學習來提高定位精度，有效減小了定位誤差。

與使用單個傳感器相比，顯而易見地，使用多個傳感器作為參考節(jié)點匯集其數(shù)據可以提高信息的準確性。但這些傳感器并非隨意組合，參考節(jié)點的選擇及數(shù)據的處理至關重要，因此許多研究者將聚類方法應用到節(jié)點選擇中以提高定位精度。Nomura等[10]使用基于層次聚類的方法來選擇屬于不同簇的參考節(jié)點，通過考慮參考節(jié)點的位置偏差來縮小用于位置估計的信標節(jié)點，從而選出合適位置的信標節(jié)點來縮小定位誤差。Guo等[11]提出一種自聚類的測量組合方法，使用通過雙曲線定位算法獲得的源位置估計用作聚類模式，調整單位RSSI值，以使估計的未知節(jié)點位置與實際位置之間的差異最小。Shi等[12]設計了一種新的基于k均值聚類的跟蹤算法，將RSSI分為減少、正常和增加三類，借此選取更符合實時情況的參考節(jié)點，提高了定位精確性和穩(wěn)定性。

上述工作在提高無線傳感器網絡中定位精度方面有一定的應用價值，然而，鮮有算法考慮定位目標分布廣且彼此相距較遠的場景。由于定位范圍廣、信標節(jié)點分布隨機且稀疏，若直接令信標節(jié)點對未知節(jié)點進行定位，不僅開銷龐大，RSSI測距信息還會受周圍環(huán)境因素影響導致定位精度下降。為了彌補這一不足，本文提出基于模糊聚類的加權協(xié)作定位算法WCFC（Weighted collaborative positioning algorithm based on fuzzy clustering），針對信標節(jié)點分布稀疏的戶外環(huán)境，將信標節(jié)點合理地劃分成若干個簇，在各個簇中將被定位過的未知節(jié)點轉化為信標節(jié)點進行協(xié)作定位，同時對RSSI值進行加權處理，盡可能地降低環(huán)境對定位精度的影響。

1 系統(tǒng)模型

WCFC算法具體應用于以下場景：在M*N的區(qū)域中，隨機分布p個信標節(jié)點和q個未知節(jié)點，通信范圍設為R。其中，信標節(jié)點配備GPS，可以獲得自身和其他信標節(jié)點的位置信息。還可以接收到未知節(jié)點的RSSI信息，利用RSSI信息獲取未知節(jié)點相對于信標節(jié)點的位置[13]。針對實際的應用環(huán)境，一般選取兩種傳播路徑損耗模型：自由空間傳播模型和對數(shù)正態(tài)分布模型[14]。自由空間傳播模型一般用于發(fā)射端與接收端之間完全無阻擋的情況下，典型的應用是衛(wèi)星通信系統(tǒng)和微波視距無線鏈路。對數(shù)正態(tài)分布模型一般用于節(jié)點發(fā)射的無線電信號在傳播過程中受到多徑、障礙物等環(huán)境影響的情況下，所以本文選用對數(shù)正態(tài)分布模型作為傳播路徑損耗模型來計算未知節(jié)點與錨節(jié)點之間的距離[15]：

其中，d是發(fā)送節(jié)點與接收節(jié)點之間的距離，RSSI是接收信號強度，P(d0)是在近地參考距離為d0（通常d0=1 m）時的接收信號強度，α是路徑損耗因子，其值取決于特定的傳播環(huán)境，λ是均值為0的高斯隨機變量。信標節(jié)點與未知節(jié)點之間的距離d可以由式(1)計算。未知節(jié)點可以發(fā)送信號也可以接收到信標節(jié)點的信息。初始定位時，本文采用傳統(tǒng)的三邊定位算法[16]，見圖1。

圖1 三邊定位模型圖

2 WCFC算法

為了降低系統(tǒng)傳輸信號的開銷和損耗，減小RSSI測距誤差對定位精度的影響，加快定位收斂速度，WCFC算法將分布稀疏的信標節(jié)點按照一定的規(guī)則分簇，在簇內進行協(xié)作定位和數(shù)據處理，用三邊定位算法將被定位的未知節(jié)點轉化為信標節(jié)點，再對RSSI信息進行加權處理。該算法分為兩個階段：分簇和定位。

分簇階段：在分簇算法的選擇上，由于傳感器距離遠，可用的參數(shù)較少，通常用于定位的聚類算法為k-均值聚類算法和模糊聚類算法[17]。前者僅利用每個節(jié)點之間的距離進行聚類，但在聚類時，某一簇可能過于孤立，導致信標節(jié)點分布不均，定位誤差過大。為了提高定位精度和資源分配的合理性，本文采用模糊聚類算法對信標節(jié)點進行聚類。WCFC算法的分簇可分為四個步驟：

步驟一：用模糊聚類算法對所有信標節(jié)點進行聚類。模糊聚類算法具體如下：

1）隨機初始化集群成員值μij，目標函數(shù)

4)計算目標函數(shù) Jm，重復 1）～4），直到 Jm的值小于指定的最小閾值或進行到預先設定的迭代次數(shù)。得到每個聚類的聚類中心cj和每簇信標節(jié)classi點。

步驟二：定義信標節(jié)點分簇規(guī)則。聚類過程中若該簇中只有兩個信標節(jié)點，則該信標節(jié)點搜尋自己相鄰的里面有三個以上信標節(jié)點的簇，然后將符合要求的相鄰簇中距離該簇最近的信標節(jié)點納入該簇范圍。若只有兩個信標節(jié)點的簇找不到符合要求的信標節(jié)點，或出現(xiàn)了只有一個信標節(jié)點的簇，則重復步驟一直到所有初始簇符合要求。

步驟三：將未知節(jié)點劃分到對應的簇中。計算所有信標節(jié)點對于簇心的距離，再利用信標節(jié)點接收到的未知節(jié)點的RSSI信息估算通信范圍內所有未知節(jié)點相對于簇心的距離，將距離簇心最遠的未知節(jié)點的距離當作簇半徑，并為該簇每一個未知節(jié)點打上唯一標記IDclassi。

步驟四：剔除簇中重復的未知節(jié)點。若該簇中的未知節(jié)點被標記了兩個及兩個以上的IDclassi，則該未知節(jié)點納入距離其最近的一個簇。

定位階段：在簇內進行基于RSSI優(yōu)化的協(xié)作定位。利用三邊定位算法對未知節(jié)點進行定位，未知節(jié)點只有能夠接收到3個及以上信標節(jié)點的信息才有被定位的可能[18]。但是當未知節(jié)點距離初始信標節(jié)點非常遠時，RSSI的測距信息因為環(huán)境影響誤差會很大?；诖?，本文提出一種協(xié)作定位算法，信標節(jié)點對遠處未知節(jié)點的定位可以通過先定位近處的未知節(jié)點傳遞實現(xiàn)，這樣系統(tǒng)不僅僅能夠通過信標節(jié)點實現(xiàn)對未知節(jié)點的定位，還可以利用未知節(jié)點間的信息傳輸來完成所有節(jié)點的定位。系統(tǒng)內所有的節(jié)點功能相同，地位對等，每一個節(jié)點都可以參與未知節(jié)點的定位，從而能夠實現(xiàn)對節(jié)點資源的充分利用，提高系統(tǒng)魯棒性。

每次對未知節(jié)點進行定位時，選取距離該未知節(jié)點最近的三個信標節(jié)點，提高定位的效率。但是該信標節(jié)點可能是在協(xié)作定位時由未知節(jié)點轉化過來的，本身位置信息存在誤差，且可能不是信號強度最好的三個信標節(jié)點。為了彌補信號強度由于環(huán)境因素而對算法結果產生誤差的缺陷，提高信號強度的完整性與準確率，算法引入RSSI優(yōu)化機制，通過為RSSI值求得一個加權系數(shù)，用加權后的RSSI值代替原始RSSI值。具體步驟如下：

步驟一：設要被定位的未知節(jié)點為Ui(x0,y0)，該點選取的三個信標節(jié)點坐標為B1(x1,y1)、B2(x2,y2)、B3(x3,y3)，未知節(jié)點接收到的信號強度為RSSIi，求得平均值：

步驟二：對于來自三個信標節(jié)點的信號強度，如果RSSImean與RSSIi相差較大，給予一個相對小的權值，反之則給予一個相對大的權值。得到權重因子ki

步驟三：得到三個信標節(jié)點修正后的RSSIi′值：

步驟四：利用步驟三得到修正后的RSSIi′，對其余的未知節(jié)點進行定位。重復步驟一到步驟三，直到所有未知節(jié)點都被定位。

3 仿真實驗

對所提出的WCFC算法進行仿真實驗，并將所得的實驗結果分別同Dv-hop[16]、三邊定位及協(xié)作定位算法[19]進行對比。定位誤差是由定位處的節(jié)點坐標和真實節(jié)點坐標之間的歐式距離[20]表示：

其中，(xM,yM)為定位處的節(jié)點坐標，(xT,yT)為真實節(jié)點坐標，d為兩者之間的歐式距離。

在一定區(qū)域內隨機稀疏部署信標節(jié)點和未知節(jié)點來模擬定位目標分布廣且彼此相距較遠的應用場景，然后使用WCFC算法對未知節(jié)點進行定位。圖2展示了500×500 m2范圍內，信標節(jié)點均勻分布30個，未知節(jié)點均勻分布200個，聚類數(shù)為5的分簇情況。

圖2 信標節(jié)點聚類結果

圖2中不同形狀的較大節(jié)點代表不同簇中的信標節(jié)點，較小的黑色圓點代表未知節(jié)點。由圖2可知分簇結果滿足了定位要求，每個簇中至少包含三個信標節(jié)點，且各簇劃分合理分布均勻，有利于下一階段定位的進行。

在邊長為500 m的區(qū)域范圍內，設置初始信標節(jié)點個數(shù)為12個，未知節(jié)點200個，初始信標節(jié)點和未知節(jié)點均遵循均勻分布，將信標節(jié)點分為3簇，其定位情況如圖3所示。

圖3 協(xié)作定位算法與本文算法的對比

圖3中橫軸是信標節(jié)點數(shù)目，縱軸是定位誤差，單位是m。從圖3中可以看出，本文算法和只應用協(xié)作定位算法都呈現(xiàn)出信標節(jié)點數(shù)量越多，定位誤差越小的結果。但是由于WCFC算法對RSSI進行了加權處理，因此相比于只應用協(xié)作定位算法，本文算法在不同信標節(jié)點數(shù)量上定位精度提高了10%～15%。

在邊長為500 m的區(qū)域內，均勻分布200個未知節(jié)點，依次均勻分布15個、20個、25個信標節(jié)點，分別用WCFC、Dv-hop、三邊定位及協(xié)作定位算法將未知節(jié)點分成4簇，其定位情況如圖4所示。

圖4 協(xié)作定位算法、Dv-hop算法和三邊定位算法與本文算法的對比

圖4中橫軸是信標節(jié)點數(shù)目，縱軸是定位誤差，單位是m。由圖4中可以看出，將本文算法的定位誤差與在等同條件下的三邊定位算法，Dv-hop算法和協(xié)作算法相比較的情況下，當信標節(jié)點數(shù)目增加時，四種算法的定位誤差都呈現(xiàn)減小的趨勢，說明增多參與定位的信標節(jié)點可以減小定位誤差。但是當信標節(jié)點數(shù)量相同時，本文算法誤差最小，說明WCFC算法在對信標節(jié)點進行最優(yōu)化分簇之后，增加了定位的有效信標節(jié)點數(shù)目，定位精度得到了有效提高。

4 結論

本文通過將聚類的思想與傳統(tǒng)定位算法相結合，給出一種基于模糊聚類的加權協(xié)作定位算法，主要解決定位時信標節(jié)點分布稀疏的野外環(huán)境對RSSI測距的影響及定位收斂速度慢的問題。通過模糊聚類，先對信標節(jié)點進行劃分，再在各個簇內進行基于RSSI加權處理的協(xié)作定位，不僅加快了定位的收斂速度，節(jié)省了系統(tǒng)能耗，還盡可能降低了由于距離、噪聲等因素對RSSI測距信息的影響。由仿真結果可以看出，在信標節(jié)點足夠多時，本文算法同Dv-hop和三邊定位算法相比定位誤差得到了很大程度地減小，但與沒有引入RSSI權值信息的協(xié)作算法的定位精度相差不大，所以只適用于信標節(jié)點稀疏的情況。未來工作可考慮將本文算法應用在動態(tài)場景中進行測試，在未知節(jié)點運動狀態(tài)下探索算法進一步優(yōu)化的方法。