一種基于改進遺傳算法的無線網絡覆蓋研究

葉劍春（山西煤炭職業技術學院 計算機系，山西 太原030031）

覆蓋優化機制成為無線傳感器網絡應用的一個重要問題[1]。目前已有很多學者對無線傳感器網絡覆蓋優化機制進行研究并取得成果。有學者研究了加權遺傳算法[2]和基于約束遺傳算法[3]的優化覆蓋機制，計算出傳感器網絡充分覆蓋指定區域所需的近似最優工作節點集，只說明該算法應用的有效性而沒有說明它應用的優越性；還有研究學者通過粒子群算法[4]實現覆蓋控制，并分析了傳感半徑對覆蓋性能的影響，但是其優化目標不考慮節點利用率所得到的優化結果，不利于延長網絡生存周期。由于無線傳感器網絡的節點由能量有限的電池供電，其大多數都部署在野外和戰場等復雜環境下，為其進行充電不太現實。因此在保證網絡覆蓋率的條件下同時延長網絡的生命周期成為傳感器網絡研究中的熱點。

隨著越來越多的大中型規模網絡采用多WLAN來進行無縫覆蓋，如何放置無線接入訪問點以使得在有限發射功率條件下達到最大網絡有效覆蓋率的問題變得越來越突出，網絡規劃迫切地需要一種優化算法來解決這個問題。目前還沒有成熟的理論和工具，雖然在基于CDMA或TDM技術的蜂窩系統中已提出許多基站放置優化算法，但都不能直接應用在WLAN環境。目前已有一些無線局域網規劃軟件可以根據無線信號強度來確定AP的放置方案，但并沒有針對大規模局域網系統的接入點放置優化算法。本文針對當前傳感器網絡的算法中存在的熱點問題提出一種改進的遺傳算法，通過設置合理的接入訪問點位置實現網絡有效覆蓋率的最大化，并有效避免小區間的同頻干擾。該算法以網絡有效覆蓋率為優化目標，改進了遺傳算法中的交叉和變異策略。實驗表明，改進的遺傳算法可有效提高網絡的覆蓋率，實現了網絡性能優化。

1 無線傳感器網絡覆蓋原理

在需要獲得較高覆蓋率的無線網絡中，通常以加大節點的布設密度來減少感知盲點出現的幾率。但是，大量冗余節點會使網絡數據傳輸產生沖突，導致能量過分消耗，造成網絡過早失效。若某節點的感知區域能被其他節點完全覆蓋，則此節點為冗余節點，可以進入休眠狀態。通過一定的算法判斷網絡中的冗余節點，在保證網絡覆蓋率最大化的同時使用盡可能少的工作節點并讓冗余節點進入休眠狀態是一種滿足網絡覆蓋要求并減小能耗的有效方法。因此，在網絡初始階段，工作節點的合理選取對提高網絡性能和降低運行成本有重要意義。與此同時，網絡能量的均衡消耗對于網絡的穩定運行和網絡壽命的延長至關重要，這就存在與覆蓋率和工作節點數相互矛盾的問題。因此需要對多個目標進行優化。

設目標區域內網格總數為m，AP備選位置共n個，預設所需的AP數量為k，該AP的有效覆蓋范圍為Di，i∈I={1，2，…，n}。則問題轉化為從 n個備選位置中選擇k個最優位置，使得總覆蓋區域 D最大化[5-6]。

本文采用Two-ray-ground模型來模擬接收信號強度分布，接收信號功率Pr為：

其中Pt為發送信號功率，Gt、Gr為發送、接收天線增益，ht、hr為發送、接收天線高度，d為信號傳輸距離，L為信道干擾。

基于上述描述，用1表示接收功率大于-60 dBm的網格，即有效覆蓋網格；用0表示接收信號功率小于-60 dBm的網格，即無效覆蓋網絡。則可得到一個m×n的矩陣M：

矩陣共n列代表備選AP的數量，每一列m個元素代表該備選AP所覆蓋區域的有效性。如：

網絡中k個AP的覆蓋率可表示為有效覆蓋的網格數量與目標區域網格總量之比，則網絡有效覆蓋率Rcov可表示為：

2 改進的遺傳算法無線網絡覆蓋

遺傳操作包括三個基本遺傳算子：選擇、交叉和變異。其中交叉和變異對算法的影響最大。交叉通過把兩個父代個體的部分結構加以替換重組而生成新個體，變異則是對群體中的個體串的某些基因位上的基因值進行改動，交叉和變異使遺傳算法的搜索能力得到提高。交叉算子因其全局搜索能力作為主要算子，變異算子因其局部搜索能力作為輔助算子。

傳統的遺傳算法采用固定的交叉和變異概率，在迭代后期可能會導致若干問題，如小的變異和交叉概率容易引起收斂緩慢和早熟等問題，而大的變異概率則會導致算法無法收斂。

為解決以上問題，本文采用了一種自適應的交叉和變異算子，使不同的個體自適應地改變交叉和變異概率。相似度較高的父代個體降低其交叉概率，而相似度低的父代個體則提高其交叉概率，以提高交叉操作的有效性，實現更有效的全局搜索；同時對適應度高的個體采用低的交叉概率，對適應度低的個體采用高的交叉概率，有利于保持種群的多樣性，加快收斂并避免陷入局部最優。自適應交叉和變異算子的計算如下：

其中 ci，j，n為第 i和第 j個父代在第 n 代的交叉概率，si，j為第i和第j個父代之間的相似度，本文中采用Hamming距 離 ，mi，n為 第 i個個體 在 第 n 代的 變 異 概 率 ，fi，n為第i個體在第n代的適應度。

如果備選AP總數量為n，k為預設的AP數量，則在該問題中可能的設置方案為種情況。本算法中采用的編碼方式將染色體I分成k個部分，每個部分用長度為l的行向量表示，對應一個AP位置的編號，l的長度為：

則染色體總長度為k×l。由于編碼后的染色體的交叉、變異范圍為2l，可能超出總量為n的可行解范圍造成溢出。為解決上述問題，需在解碼時進行相應的線性變換，將染色體的值轉換到[0，n]范圍內。

式(9)中，ID′為轉換后的十進制編號值并且 0≤ID′≤n。

算法對于子代的選擇方式采用輪盤賭算子。將整個種群視為一個圓盤，根據每個染色體適應度值確定該染色體的權重，通過產生的隨機指針選擇要復制的子代[7]。

交叉是對任意兩個個體按某種方式互換其部分基因，從而形成兩個新的個體，是遺傳算法中產生新個體的主要方法。變異是指將個體編碼串中的某些基因值用其他基因值來替換，生成一個新的個體。本文算法中交叉和變異過程采用均勻交叉算子和均勻變異算子，將每個染色體上對應的基因以相同的概率進行交叉、變異。

適應度用來度量個體在優化計算中可能到達最優解的優良程度，個體的適應度通過適應度函數產生。直接用有效覆蓋率作為適應度函數，則適應度函數f1(I)可表示為：

其中cov表示目標區域內有效覆蓋的網格數量，m為區域內網格總數量。仿真結果顯示，式(10)所示的適應度函數在實際算法的應用中存在收斂速度過快或過慢的問題，容易收斂于局部最優值，而不能準確達到全局最優解。下面對f1(I)進行部分改進，做線性變換得到f2(I)[8]：

式(11)中的系數 a、b使 f2(I)滿足：

c的取值為f的最大值與均值的比例。由式(11)、式(12)可得：

由式(13)得到系數 a、b，進而由式(11)得到 f2(I)。

在上述適應度函數的基礎上，提出第三種適應度函數f3(I)：

f3(I)的值在一定范圍內隨有效覆蓋率的提高呈指數增長。

3 仿真結果分析

本文所有的實驗都是在PC P4 T2310 1.86 GHz、2 GB RAM、Inte182865G顯卡的計算機上完成，實驗環境為MATLAB7.0，為了驗證本文提出的改進算法的有效性，根據無線傳感器網絡確定性覆蓋方法[9-11]，選取的目標區域為160 m×160 m的正方形自由區域，網格劃分的步長為2 m，則總網格數為6 400個。在目標區域中隨機生成40個不相鄰點作為備選位置，取預設AP數為3，則所有可能的情況為即9 880個。無線接收信號強度分布模型采用Two-ray-ground模型，接收信號功率大于-60 dBm為有效覆蓋網格。算法核心在于從40個備選位置中選擇3個最優AP放置點，使目標區域內的有效覆蓋率最大化。設置遺傳算法的參數：初始交叉率為0.1，初始變異率為 0.6，迭代次數為200。

圖1和圖2分別為算法運行20次適應度均值。從圖中可以看出，算法總體收斂性很好。對于適應度函數1，算法在40代前可達到收斂，并對種群數量變化的靈敏度不大。對于適應度函數2，算法收斂速度與適應度函數1相比較慢，種群數量對算法性能影響較大，數量為50的種群性能優于數量為5的種群。進一步分析表明，并不是種群數量越大，算法性能越好。若種群數量過大易造成系統數據量過大，影響運算效率。

圖1 不同種群數量優化值比較(適應度函數1)

圖2 不同種群數量優化值比較(適應度函數2)

從上面兩幅圖中可以看出，適應度函數2可達到的最大覆蓋率最高，另外適應度函數2的最大覆蓋率高于適應度函數1。由于適應度函數是覆蓋率的反映，引導著算法收斂的方向，但并不與覆蓋率完全正相關。在60代左右，適應度函數2與覆蓋率進化方向產生差別導致噪聲產生。

表1所示為兩種適應度函數仿真結果比較，可見適應度函數2可達的最高覆蓋率較高，適應度函數1的收斂速度比適應度函數2快，從整體性能來看，適應度函數2性能較好。

表1 兩種適應度函數比較

無線傳感器網絡極大地提高了人們認識和改造世界的能力。而網絡覆蓋控制作為無線傳感器網絡實施過程中的一個重要問題，反映了網絡所能提供的感知服務質量。本文立足于無線傳感器網絡的優化覆蓋問題，提出了一種改進的遺傳算法無線傳感器網絡覆蓋優化機制，通過與兩種適應度函數比較、仿真實驗結果表明，該優化機制能更有效地跳出局部最優，獲得更精確的結果，從而更好更有效地實現了無線傳感器網絡布局的全局優化。

[1]毛鶯池，陳力軍，陳道蓄，等.無線傳感器網絡覆蓋控制技術研究[J].計算機科學，2007，34(3)：20-22.

[2]汪學清，楊永田，孫亭，等.無線傳感器網絡中基于網格的覆蓋問題研究[J].計算機科學，2006，33(11)：38-39，78.

[3]屈斌，胡訪宇.高效節能的無線傳感器網絡路由協議研究[J].計算機仿真，2008，25(5)：113-116.

[4]周永華，李鵬，毛宗源.一種新的混合雜交方法及其在約束優化中的應用[J].計算機工程與應用，2006，42(6)：48-50.

[5]HERRERA F，LOZANO M.Gradual distributed Real Coded genetic algorithms[J].IEEE Trans on Evolutionary Computation，2000，5(1)：43-63.

[6]張輪.一種無線傳感器網絡覆蓋的粒子群優化方法[J].同濟大學學報(自然科學版)，2009，37(2)：262-266.

[7]劉麗萍，王智，孫優賢.無線傳感器網絡部署及其覆蓋問題研究[J].電子與信息學，2006，28(9)：1752-175.

[8]杜輝，肖德貴，羅娟，等.一種無線傳感器網絡覆蓋度確定算法[J].計算機仿真，2007，24(12)：117-120.

[9]YOUNIS O，FAHMY S.HEED：a hybrid，energy-efficient，distributed clustering approach for Ad hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004，3(4)：660-669.

[10]李捷，劉先省，韓志杰.基于ARMA的無線傳感器網絡流量預測模型的研究[J].電子與信息學報，2007，29(5)：1224-1227.

[11]YE M，LI C F，CHEN G H，et al.An energy efficient clustering scheme in wireless sensor networks[J].International Journal of Ad Hoc&Sensor Wireless Networks，2007，3(2)：99-119.