常龐帆 仉俊峰 仉斡

(東北林業(yè)大學(xué)，哈爾濱，150040) (中山大學(xué))

林業(yè)無線傳感器網(wǎng)絡(luò)，是一種由部署在待檢測區(qū)域，具有感知、計算與通信能力的微型傳感器組成的自組織分布式無線網(wǎng)絡(luò)系統(tǒng)。這些節(jié)點(diǎn)通過無線通信方式組成一個多跳自組織網(wǎng)絡(luò)，從而協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息，并發(fā)送給觀察者。在實(shí)際運(yùn)用中，這些傳感器節(jié)點(diǎn)通常是被飛機(jī)撒播在指定的監(jiān)測區(qū)域中，它們的位置是隨機(jī)的、未知的，因此，傳感器節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)應(yīng)用中的關(guān)鍵技術(shù)之一，是無線傳感器網(wǎng)絡(luò)實(shí)現(xiàn)目標(biāo)識別、監(jiān)控、跟蹤等眾多功能的前提[1-2]。

現(xiàn)有的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法通過節(jié)點(diǎn)相互傳播信息，未知節(jié)點(diǎn)在收集信息后計算與自己相鄰錨節(jié)點(diǎn)的距離，再采用最小二乘法求解自己的位置[3]。根據(jù)是否通過硬件測距，定位算法可分為依據(jù)測距、依據(jù)非測距。依據(jù)測距的定位算法，一般通過能量強(qiáng)度、到達(dá)時間、到達(dá)時間差、到達(dá)角度等參數(shù)測量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離，然后再采用最小二乘法求解未知節(jié)點(diǎn)的精確位置。依據(jù)非測距的定位算法，一般通過質(zhì)心估計、距離估計等方式直接估計節(jié)點(diǎn)的位置或在估計節(jié)點(diǎn)之間的距離之后，再采用最小二乘法求解未知節(jié)點(diǎn)的位置。由于無論通過硬件測距方式，還是通過估距方式，都會產(chǎn)生距離誤差，采用最小二乘法求解節(jié)點(diǎn)的位置會形成誤差累積，影響定位精度[4-8]。

遺傳算法起源于對生物系統(tǒng)進(jìn)行的計算機(jī)模擬研究。是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索方法，通過采用“適者生存”的原則，在潛在的解決方案種群中逐次產(chǎn)生一個近似最優(yōu)的方案[9-10]。遺傳算法具有良好的全局搜優(yōu)性，并且收斂速度快，具有可擴(kuò)展性，易于同其它技術(shù)混合使用，因此，被廣泛地運(yùn)用到很多科研領(lǐng)域中[11]。由于傳統(tǒng)的遺傳算法存在過早收斂問題，筆者對遺傳定位算法進(jìn)行了改進(jìn)，提出了一種新的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法；經(jīng)仿真驗證，改進(jìn)遺傳算法是一種較好的林業(yè)系統(tǒng)中無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法。

1 定位算法的數(shù)學(xué)模型

假設(shè)待定位無線傳感器網(wǎng)絡(luò)中共M+N個節(jié)點(diǎn)，其中已知節(jié)點(diǎn)(即錨節(jié)點(diǎn))數(shù)為M，未知節(jié)點(diǎn)數(shù)為N。通過某種測距方式，每個未知節(jié)點(diǎn)知道在通信半徑內(nèi)所有已知節(jié)點(diǎn)與自己距離，則可利用最小二乘法求得未知節(jié)點(diǎn)位置。設(shè)已知節(jié)點(diǎn)坐標(biāo)為Ai(xi，yi)，i=1、2、…、M；未知節(jié)點(diǎn)坐標(biāo)為(x，y)，其與已知節(jié)點(diǎn)距離為d1、d2、…、dM；則可建立方程組(1)。

(1)

求解方程組(1)即可得到未知節(jié)點(diǎn)位置。當(dāng)錨節(jié)點(diǎn)數(shù)目≥3時，此方程是欠定方程。在實(shí)際操作中，由于環(huán)境硬件因素的影響，測量得到的距離會產(chǎn)生誤差，而求解此方程時運(yùn)用最小二乘法也會造成誤差累積，因此，需要引入遺傳算法減小誤差。

2 改進(jìn)型遺傳定位算法

遺傳算法，是一種借鑒自然界生物的遺傳和進(jìn)化過程而形成的自適應(yīng)全局隨機(jī)搜索與優(yōu)化算法。它將問題的所有可能解組成一個種群，將每一個可能解視為種群的個體。從選定的初始種群出發(fā)，在整個種群空間內(nèi)隨機(jī)搜索，按照一定的適應(yīng)度函數(shù)評估每一個體，循環(huán)使用選擇、交義、變異三種遺傳算子，使問題的解不斷進(jìn)化，直至搜索到最優(yōu)解。

傳統(tǒng)遺傳算法效率較低，容易出現(xiàn)過早收斂問題。筆者在綜合考慮了傳統(tǒng)遺傳算法的優(yōu)缺點(diǎn)之后，提出了一種新的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法。

2.1 種群初始化

種群初始化是為了產(chǎn)生初始的染色體種群，為遺傳算法的計算打好基礎(chǔ)。首先需要通過編碼把問題的可行解從其解空間轉(zhuǎn)換到遺傳算法的搜索空間。遺傳算法的編碼方式，主要有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼、動態(tài)參數(shù)編碼等，為了保證群體穩(wěn)定性，本文采用二進(jìn)制編碼。二進(jìn)制編碼中，本文將每個個體的基因值用(0，1)區(qū)問均勻分布的隨機(jī)數(shù)表示，未知節(jié)點(diǎn)的縱坐標(biāo)與橫坐標(biāo)的編碼長度均設(shè)為10位。

對產(chǎn)生的待計算的初始種群，通常做法是確定基因的取值范圍，在取值范圍內(nèi)隨機(jī)生成初始種群；但是，這樣產(chǎn)生的初始種群分布過于隨機(jī)，對提高算法的效率沒有太大幫助。文獻(xiàn)[11]提出，初始種群應(yīng)根據(jù)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離進(jìn)行篩選。本文采用類似的方法，即在不同錨節(jié)點(diǎn)通信區(qū)域的重疊范圍內(nèi)進(jìn)行隨機(jī)初始種群生成，篩選公式：

式中：i=1、2、…、n；xi為節(jié)點(diǎn)i的橫坐標(biāo)；yi為節(jié)點(diǎn)i的縱坐標(biāo)；di為節(jié)點(diǎn)i與錨節(jié)點(diǎn)之間的距離。

2.2 適應(yīng)度函數(shù)設(shè)置

適應(yīng)度函數(shù)也稱評價函數(shù)，是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個體好壞的標(biāo)準(zhǔn)。適應(yīng)度的值越大，代表對應(yīng)染色體越接近最優(yōu)解。

由方程組(1)可以設(shè)遺傳算法中適應(yīng)度函數(shù)為：

式中：x、y為未知節(jié)點(diǎn)坐標(biāo)；xi、yi為錨節(jié)點(diǎn)坐標(biāo)；di為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)(xi，yi)的測量距離。

將定位問題轉(zhuǎn)化為求解無約束極值問題。每次定位一個未知節(jié)點(diǎn)的位置時，調(diào)用一次遺傳算法，染色體編碼即為未知節(jié)點(diǎn)的待定坐標(biāo)，上式最優(yōu)解即為未知節(jié)點(diǎn)的估計位置。

2.3 選擇算子設(shè)計

遺傳算法中的選擇操作，是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運(yùn)算，用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。常用的選擇算子，有輪盤賭選擇、隨機(jī)競爭選擇、精英選擇、期望值選擇等。

為了最大限度保留優(yōu)質(zhì)基因，本文采用的選擇方式：根據(jù)適應(yīng)度函數(shù)式計算出的值進(jìn)行排序，將適應(yīng)度最高的兩個個體完整復(fù)制到下一代，適應(yīng)度最低的個體直接淘汰，其余個體則根據(jù)交叉算子與變異算子正常進(jìn)行操作。與文獻(xiàn)[6]中的選擇算子相比，本文采用的方法可以更好地保證各代種群的優(yōu)質(zhì)性，同時避免早期的高適應(yīng)度個體迅速占據(jù)種群，使后期的種群中因個體的適應(yīng)度相差不大而導(dǎo)致種群停止進(jìn)化。

2.4 交叉算子設(shè)計

遺傳算法的交叉操作，是對兩個相互配對的染色體，按某種方式相互交換其部分基因，形成兩個新的個體。通過交叉操作，一方面，可以使父代群體中優(yōu)良染色體的特性，在子代中繼續(xù)保存；另一方面，可以使子代染色體具有多樣性。常用的方法，主要有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、算術(shù)交叉等。

定義交叉概率：

式中：pc1、pc2∈(0，1)；Fg為個體g的自適應(yīng)度函數(shù)值；Fgb為最優(yōu)個體自適應(yīng)度函數(shù)值；Favg為自適應(yīng)度函數(shù)的平均值；Farg為自適應(yīng)度函數(shù)的實(shí)際參數(shù)值。

對于每代需要進(jìn)行交叉操作的染色體，按如下步驟進(jìn)行：

對每條染色體隨機(jī)產(chǎn)生一個(0，1)之間隨機(jī)數(shù)，將每條染色體的隨機(jī)數(shù)與其交叉概率進(jìn)行比較，若隨機(jī)值小于交叉概率，則將該染色體定義為待交叉染色體，形成待交叉染色體集合。如果集合數(shù)目是偶數(shù)，順序兩兩交叉；如果集合數(shù)目是奇數(shù)，順序兩兩交叉后，集合中最后一個染色體不交叉，直接進(jìn)入下一代。對于每一對交叉的染色體，通過隨機(jī)數(shù)確定交叉的位置。

2.5 變異

遺傳算法中的變異運(yùn)算，是將個體染色體編碼串中的某些基因座上的基因值，用該基因座上的其它等位基因替換，形成一個新的個體。通過變異操作，可以使遺傳算法脫離局部最優(yōu)解，繼續(xù)計算全局最優(yōu)解。常用的方法，主要有基本位變異、均勻變異、邊界變異、非均勻變異、高斯變異等。

定義變異概率：

式中：pm1、pm2∈(0.01，0.10)；Fg為個體g的自適應(yīng)度函數(shù)值；Fgb為最優(yōu)個體自適應(yīng)度函數(shù)值；Favg為自適應(yīng)度函數(shù)的平均值。

對于每代需要進(jìn)行變異操作的染色體，按如下步驟進(jìn)行：

對每條染色體隨機(jī)產(chǎn)生一個(0，1)之間隨機(jī)數(shù)，將每條染色體的隨機(jī)數(shù)與其變異概率進(jìn)行比較，若隨機(jī)值小于變異概率，選擇對其進(jìn)行變異。具體的變異操作，是通過隨機(jī)數(shù)決定變異位置，并對該位進(jìn)行取反完成。

設(shè)遺傳算法中染色體數(shù)目為m，每條染色體編碼長度為n，則每條染色體為s1、s2、…、sm，可以構(gòu)成矩陣S(m)。

在二進(jìn)制編碼條件下，有時會出現(xiàn)一種情況，即矩陣S(m)的某一列全為相同的元素，即全為0，或全為1。此時通過交換操作，不能改變該位的值，這種情況會導(dǎo)致只能得出局部最優(yōu)解，無法接近全局最優(yōu)解。傳統(tǒng)的突變操作，僅相當(dāng)于對矩陣S(m)行上的數(shù)值進(jìn)行突變，沒有辦法解決這種某一基因位單調(diào)的問題。因此在變異操作階段，除了對染色體進(jìn)行變異之外，還需要對這種單調(diào)基因位進(jìn)行檢測與位變異。

雖然本文提出的變異運(yùn)算操作比文獻(xiàn)提到的更加復(fù)雜，但可以有效提高算法的精度，避免局部最優(yōu)解的出現(xiàn)。

3 仿真實(shí)驗

為更準(zhǔn)確驗證本文提出的算法的有效性，在windows7操作系統(tǒng)下的Matlab平臺上進(jìn)行仿真模擬實(shí)驗。隨機(jī)在100×100的區(qū)域中選取100個節(jié)點(diǎn)，其中20個為錨節(jié)點(diǎn)，80個為未知節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑為40。遺傳算法中，具體參數(shù)取值為：種群數(shù)目為20，交叉概率pc1=0.6、pc2=0.4，變異概率pm1=0.06、pm2=0.04，最大迭代次數(shù)為100。

3.1 算法仿真結(jié)果

根據(jù)上述數(shù)據(jù)進(jìn)行仿真實(shí)驗，原始節(jié)點(diǎn)分布如圖1所示，經(jīng)過遺傳算法計算后的定位結(jié)果如圖2所示。由圖1、圖2可見：定位結(jié)果基本都能準(zhǔn)確定位到未知節(jié)點(diǎn)處。說明改進(jìn)型遺傳算法具有良好的定位性能。

〇為錨節(jié)點(diǎn)；△為未知節(jié)點(diǎn)。

〇為錨節(jié)點(diǎn)；△為未知節(jié)點(diǎn)；*為預(yù)測節(jié)點(diǎn)。

3.2 性能比較

為分析改進(jìn)型遺傳算法與傳統(tǒng)遺傳算法的性能差異，在相同參數(shù)條件下用兩種算法進(jìn)行計算，其迭代次數(shù)與適應(yīng)度值變化關(guān)系如圖3所示。由圖3可見：隨著迭代次數(shù)的增加，改進(jìn)型遺傳算法的收斂性優(yōu)于傳統(tǒng)遺傳算法。

圖3 適應(yīng)度變化情況

在其余運(yùn)行條件相同情況下，通過改變錨節(jié)點(diǎn)數(shù)目得到的兩種算法的平均誤差如圖4所示。由圖4可見：在錨節(jié)點(diǎn)數(shù)目不同情況下，改進(jìn)型遺傳算法的精確度始終高于傳統(tǒng)型遺傳算法。

圖4 錨節(jié)點(diǎn)數(shù)目與平均誤差關(guān)系

4 結(jié)束語

本文介紹了定位算法的數(shù)學(xué)模型，并利用遺傳算法求解該數(shù)學(xué)模型的最優(yōu)解。對現(xiàn)有遺傳算法進(jìn)行了改進(jìn)，提高了算法的運(yùn)行效率，優(yōu)化了運(yùn)行步驟，避免了局部最優(yōu)解的形成。通過仿真實(shí)驗驗證，改進(jìn)型遺傳算法加快了收斂速度，也提高了對未知節(jié)點(diǎn)進(jìn)行定位的精度，可以較好地解決無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題。