基于zigbee和量子遺傳算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)研究①

， ， ，

(長安大學(xué)汽車學(xué)院，陜西 西安 710064)

0 引 言

隨著傳感器技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無線通信技術(shù)的迅速發(fā)展，大規(guī)模分布式傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)在生物醫(yī)療、環(huán)境監(jiān)測、軍事國防等領(lǐng)域應(yīng)用越來越廣泛，WSN已成為當(dāng)今世界最熱門的研究領(lǐng)域之一[1][2]。國內(nèi)外許多學(xué)者對WAN節(jié)點定位做了大量研究，如Benha University的Mohamed等人提出將整個網(wǎng)絡(luò)劃分為多個子區(qū)域并分別進(jìn)行未知節(jié)點定位的改進(jìn)的DV-Hop定位方法[3][4]；南京郵電大學(xué)的王萍萍提出的一種將TDOA算法和RSSI算法組合的定位方法，其根據(jù)錨節(jié)點離未知節(jié)點的距離長短選擇不同的算法[5][6]；武漢理工大學(xué)的王曉麗提出的基于模擬退火算法對DV-Hop算法的平均跳距進(jìn)行修正的定位方法[7]。這些定位方法與傳統(tǒng)的節(jié)點定位方法相比精度得到提高，但對更高精度的應(yīng)用場合則不能滿足要求，同時定位響應(yīng)速度也有待提高。

提出一種基于量子遺傳算法的無線傳感器網(wǎng)絡(luò)定位技術(shù)，通過分析未知節(jié)點周邊錨節(jié)點的數(shù)量，將定位情況進(jìn)行分類，依據(jù)未知節(jié)點與錨節(jié)點的測量距離，建立定位優(yōu)化模型，最后用量子遺傳算法對模型求解。仿真結(jié)果表明，量子遺傳算法比傳統(tǒng)遺傳算法有更出色的收斂性，在節(jié)點定位精度方面也比傳統(tǒng)DV-Hop算法更高，可以應(yīng)用于多數(shù)高精度、高實時性定位場合。

1 定位模型與算法分析

1.1 節(jié)點初始位置獲取

首先，網(wǎng)絡(luò)中的錨節(jié)點向它的鄰近節(jié)點廣播自己的位置信息，接收節(jié)點接收來自錨節(jié)點跳數(shù)信息同時忽略來自同一錨節(jié)點的大跳數(shù)數(shù)據(jù)，未知節(jié)點獲取鄰近錨節(jié)點的位置并測得與鄰近錨節(jié)點的距離。根據(jù)未知節(jié)點周圍錨節(jié)點數(shù)量可分為以下幾種情況獲取初始位置[8]：

未知節(jié)點周圍錨節(jié)點個數(shù)大于等于三，可以通過三邊測量法或三角測量法計算未知節(jié)點坐標(biāo)。如下圖1所示：

圖1 三邊測量法計算未知節(jié)點坐標(biāo)

已知三個錨節(jié)點U1、U2、U3的坐標(biāo)(UX1、UY1)、(UX2、UY2)、(UX3、UY3)及到未知節(jié)點K(XK、YK)的距離d1、d2、d3，K坐標(biāo)可由式1-1計算得到。

(1)

1) 如果未知節(jié)點(XK、YK)在一跳內(nèi)有兩個鄰居錨節(jié)點，則分別以錨節(jié)點U(UX1、UY1)、U(UX2、UY2)為圓心，以網(wǎng)絡(luò)節(jié)點通信半徑R為圓半徑作圓，并在如圖2所示陰影區(qū)域內(nèi)采樣，采樣點滿足下式(1-2)時保存作為未知節(jié)點初始位置，采樣點門限為N。

圖2 一跳內(nèi)有兩個錨節(jié)點

(2)

其中，DX,Ui為未知節(jié)點與錨節(jié)點U測量距離，δ為最大誤差。

2) 如果未知節(jié)點(XK、YK)在一跳內(nèi)僅有一個鄰居錨節(jié)點，則分別以該錨節(jié)點U(UX1、UY1)和一個距離該未知節(jié)點N跳的錨節(jié)點為圓心，以網(wǎng)絡(luò)節(jié)點通信半徑R和N×R為半徑作圓，并在如圖3所示的陰影區(qū)域?qū)?jié)點初始位置采樣，采樣點滿足下式(1-3)時，保存采樣點。

圖3 一跳內(nèi)僅有一個錨節(jié)點

(3)

3) 如果未知節(jié)點周圍沒有鄰居錨節(jié)點，則以距離未知節(jié)點最小距離的錨節(jié)點為圓心，以相應(yīng)的通信半徑倍數(shù)為半徑作圓，并在上述圖相應(yīng)陰影位置對未知節(jié)點采樣。若經(jīng)過采樣后采樣點分別為A1(X1、Y1)、A2(X2、Y2)…AN(XN、YN)，則未知節(jié)點的估計初始位置如式(4)所示：

(4)

1.2 量子遺傳算法優(yōu)化設(shè)計

算法優(yōu)化過程中，未知節(jié)點根據(jù)周圍錨節(jié)點數(shù)量、位置及測量距離，利用量子遺傳算法對初始位置進(jìn)行迭代優(yōu)化[9]。

步驟一：在傳感器網(wǎng)絡(luò)內(nèi)隨機(jī)產(chǎn)生M+N個節(jié)點的網(wǎng)絡(luò)拓?fù)鋱D，其中M為錨節(jié)點個數(shù)，N為未知節(jié)點個數(shù)。

步驟二：根據(jù)上述節(jié)點約束條件，對所有滿足約束條件的采樣點采用量子比特的概率幅進(jìn)行編碼，以產(chǎn)生N條量子染色體， 由它們組成初始種群。

在量子遺傳算法中，可用量子比特編碼方式對染色體進(jìn)行編碼。一個量子比特有兩個基本狀態(tài)|0和|1，還可以對兩種基本形態(tài)進(jìn)行線性組合成疊加態(tài)，如式(5)所示：

|ε=α|0+β|1

(5)

其中，|α|2+|β|2=1，α、β是一對復(fù)數(shù)，成為量子態(tài)的概率幅。

用一個量子比特表示基因的兩種狀態(tài)，兩個量子比特表示基因的四種狀態(tài)，那么K個量子比特可表示基因的2k個狀態(tài)，則K個量子比特的概率可用式(6)表示：

(6)

步驟三：計算上述每個采樣點的適應(yīng)度值并記錄最優(yōu)個體，適應(yīng)度函數(shù)如式(7)所示，并保存最佳個體和相應(yīng)的適應(yīng)度值。

(7)

步驟四：對所有的采樣點，參照步驟三記錄的適應(yīng)度值，按照輪盤賭選擇法對父代進(jìn)行選擇產(chǎn)生新一代個體。高適應(yīng)度的個體被選擇的概率高，低適應(yīng)度個體被選擇的概率低。其個體i被選擇的概率為：

(8)

步驟五：通過量子旋轉(zhuǎn)門對量子染色體進(jìn)行變異操作，以更新量子位的概率幅，從而達(dá)到基因變異、產(chǎn)生新一代個體的效果。量子旋轉(zhuǎn)門如式(9)所示：

(9)

其中，θi為量子旋轉(zhuǎn)角，可以調(diào)整其大小和方向，(α′,β′)T為更新后個體。

步驟六：記錄量子旋轉(zhuǎn)門變異后的個體數(shù)據(jù)，保存最佳個體，并比較目標(biāo)值，若目標(biāo)值小于最佳個體，則將最優(yōu)解作為下一次迭代值，進(jìn)行不斷循環(huán)迭代。

步驟七：若經(jīng)過迭代的最優(yōu)解滿足目標(biāo)值的中止條件，則輸出最優(yōu)解并退出。

2 仿真分析

基于Matlab平臺，在10m×10m的矩形區(qū)域內(nèi)隨機(jī)分布35個傳感器節(jié)點，設(shè)置錨節(jié)點比例為40%，形成無線傳感器網(wǎng)絡(luò)。采用遺傳算法對未知節(jié)點位置進(jìn)行優(yōu)化時，設(shè)置最大迭代次數(shù)為100，交叉概率PC為0.6，變異概率Pm為0.1，每次采樣100個有效樣本進(jìn)行仿真。

圖4為經(jīng)過量子遺傳算法優(yōu)化后未知節(jié)點在無線傳感器網(wǎng)絡(luò)中的分布。其中藍(lán)色為初始節(jié)點分布，紅色為優(yōu)化后的未知節(jié)點位置。

圖4 算法優(yōu)化后未知節(jié)點分布示意圖

由圖4可以看出，使用量子遺傳算法對無線傳感器網(wǎng)絡(luò)定位，對絕大多數(shù)未知節(jié)點的定位十分精確，但也有少量幾個未知節(jié)點的定位出現(xiàn)很大的偏差，其原因可能是這幾個未知節(jié)點處于整個網(wǎng)絡(luò)的邊緣地帶，其周圍沒有錨節(jié)點可供量子遺傳算法進(jìn)行抽樣、參考優(yōu)化，如兩個處于網(wǎng)絡(luò)邊界的未知節(jié)點(0、10)和(0、1)。

圖5 任意五個未知節(jié)點最優(yōu)值變化

圖6 經(jīng)典DV-Hop算法每個節(jié)點誤差

圖7 經(jīng)典DV-Hop算法每個節(jié)點均方差

圖8 智能停車場總體架構(gòu)

如圖5所示為抽取無線傳感器網(wǎng)絡(luò)中任意五個未知節(jié)點的最優(yōu)值變化過程。可以看出，五個隨機(jī)節(jié)點中紅色節(jié)點在時刻5就完成了迭代優(yōu)化，之后，該未知節(jié)點位置定位未出現(xiàn)波動；同時隨機(jī)節(jié)點中最晚完成迭代的黃色節(jié)點也只到20時刻。可以看出，量子遺傳算法有較高的優(yōu)化收斂速度，在實時性要求較高的場合可以得到應(yīng)用。

如圖6和圖7所示為采用經(jīng)典的DV-Hop算法進(jìn)行節(jié)點定位時每個節(jié)點的定位誤差和均方差。可以看出參與定位的未知節(jié)點中有靠近三分之一的節(jié)點定位誤差超過15%，甚至有兩個節(jié)點的誤差超過了20%，且對于不同的節(jié)點，其定位精度差異較大，定位精度波動明顯，對于重要的定位應(yīng)用場合，顯然該算法不能滿足精度、穩(wěn)定性的要求。

3 量子遺傳定位算法在小區(qū)停車場的應(yīng)用

隨著社會經(jīng)濟(jì)水平的不斷發(fā)展提高，私家車數(shù)量越來越多，傳統(tǒng)的地下停車場僅僅對車輛安全性進(jìn)行考慮，已經(jīng)越來越不能滿足用戶需求。本文通過對停車場運行效率和安全性進(jìn)行考慮，設(shè)計一套基于zigbee的智能停車場管理系統(tǒng)[10]。智能停車場管理系統(tǒng)總體架構(gòu)如圖8所示：

4 結(jié) 語

通過查閱相關(guān)資料了解無線傳感器網(wǎng)絡(luò)在各種應(yīng)用場合的需求，對比、分析了現(xiàn)有無線傳感器網(wǎng)絡(luò)節(jié)點定位方法的不足，提出了一套基于量子遺傳算法的無線傳感器網(wǎng)絡(luò)定位算法。算法根據(jù)未知節(jié)點周圍錨節(jié)點數(shù)量，將定位情況進(jìn)行分類，建立節(jié)點定位優(yōu)化模型，然后通過量子比特編碼方式對染色體編碼，對上述優(yōu)化模型的采樣區(qū)域進(jìn)行采樣，并使用傳統(tǒng)輪盤賭選擇法選擇采樣的初代群體，最后通過量子旋轉(zhuǎn)門對染色體進(jìn)行變異、不斷迭代，直到達(dá)到設(shè)定的目標(biāo)值。仿真結(jié)果表明：基于量子遺傳算法的無線傳感器網(wǎng)絡(luò)定位算法能非常精確的完成定位，同時定位的穩(wěn)定性和實時性也優(yōu)于傳統(tǒng)的DV-Hop算法，可以運用在各種應(yīng)用場合。