， ， ，

(長(zhǎng)安大學(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)測(cè)、軍事國(guó)防等領(lǐng)域應(yīng)用越來越廣泛，WSN已成為當(dāng)今世界最熱門的研究領(lǐng)域之一[1][2]。國(guó)內(nèi)外許多學(xué)者對(duì)WAN節(jié)點(diǎn)定位做了大量研究，如Benha University的Mohamed等人提出將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)子區(qū)域并分別進(jìn)行未知節(jié)點(diǎn)定位的改進(jìn)的DV-Hop定位方法[3][4]；南京郵電大學(xué)的王萍萍提出的一種將TDOA算法和RSSI算法組合的定位方法，其根據(jù)錨節(jié)點(diǎn)離未知節(jié)點(diǎn)的距離長(zhǎng)短選擇不同的算法[5][6]；武漢理工大學(xué)的王曉麗提出的基于模擬退火算法對(duì)DV-Hop算法的平均跳距進(jìn)行修正的定位方法[7]。這些定位方法與傳統(tǒng)的節(jié)點(diǎn)定位方法相比精度得到提高，但對(duì)更高精度的應(yīng)用場(chǎng)合則不能滿足要求，同時(shí)定位響應(yīng)速度也有待提高。

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

1 定位模型與算法分析

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

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

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

圖1 三邊測(cè)量法計(jì)算未知節(jié)點(diǎn)坐標(biāo)

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

(1)

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

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

(2)

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

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

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

(3)

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

(4)

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

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

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

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

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

|ε=α|0+β|1

(5)

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

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

(6)

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

(7)

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

(8)

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

(9)

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

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

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

2 仿真分析

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

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

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

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

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

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

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

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

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

如圖6和圖7所示為采用經(jīng)典的DV-Hop算法進(jìn)行節(jié)點(diǎn)定位時(shí)每個(gè)節(jié)點(diǎn)的定位誤差和均方差?？梢钥闯鰠⑴c定位的未知節(jié)點(diǎn)中有靠近三分之一的節(jié)點(diǎn)定位誤差超過15%，甚至有兩個(gè)節(jié)點(diǎn)的誤差超過了20%，且對(duì)于不同的節(jié)點(diǎn)，其定位精度差異較大，定位精度波動(dòng)明顯，對(duì)于重要的定位應(yīng)用場(chǎng)合，顯然該算法不能滿足精度、穩(wěn)定性的要求。

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

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

4 結(jié) 語

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