林業(yè)無線傳感器網(wǎng)絡節(jié)點定位技術(shù)1)

常龐帆 仉俊峰 仉斡

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

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

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

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

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

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

(1)

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

2 改進型遺傳定位算法

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

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

2.1 種群初始化

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

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

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

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

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

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

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

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

2.3 選擇算子設(shè)計

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

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

2.4 交叉算子設(shè)計

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

定義交叉概率：

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

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

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

2.5 變異

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

定義變異概率：

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

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

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

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

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

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

3 仿真實驗

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

3.1 算法仿真結(jié)果

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

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

〇為錨節(jié)點；△為未知節(jié)點；*為預測節(jié)點。

3.2 性能比較

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

圖3 適應度變化情況

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

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

4 結(jié)束語

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