一種基于改進(jìn)遺傳算法的無線網(wǎng)絡(luò)覆蓋研究

葉劍春（山西煤炭職業(yè)技術(shù)學(xué)院 計算機(jī)系，山西 太原030031）

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

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

1 無線傳感器網(wǎng)絡(luò)覆蓋原理

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

設(shè)目標(biāo)區(qū)域內(nèi)網(wǎng)格總數(shù)為m，AP備選位置共n個，預(yù)設(shè)所需的AP數(shù)量為k，該AP的有效覆蓋范圍為Di，i∈I={1，2，…，n}。則問題轉(zhuǎn)化為從 n個備選位置中選擇k個最優(yōu)位置，使得總覆蓋區(qū)域 D最大化[5-6]。

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

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

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

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

網(wǎng)絡(luò)中k個AP的覆蓋率可表示為有效覆蓋的網(wǎng)格數(shù)量與目標(biāo)區(qū)域網(wǎng)格總量之比，則網(wǎng)絡(luò)有效覆蓋率Rcov可表示為：

2 改進(jìn)的遺傳算法無線網(wǎng)絡(luò)覆蓋

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

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

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

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

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

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

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

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

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

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

其中cov表示目標(biāo)區(qū)域內(nèi)有效覆蓋的網(wǎng)格數(shù)量，m為區(qū)域內(nèi)網(wǎng)格總數(shù)量。仿真結(jié)果顯示，式(10)所示的適應(yīng)度函數(shù)在實際算法的應(yīng)用中存在收斂速度過快或過慢的問題，容易收斂于局部最優(yōu)值，而不能準(zhǔn)確達(dá)到全局最優(yōu)解。下面對f1(I)進(jìn)行部分改進(jìn)，做線性變換得到f2(I)[8]：

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

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

由式(13)得到系數(shù) a、b，進(jìn)而由式(11)得到 f2(I)。

在上述適應(yīng)度函數(shù)的基礎(chǔ)上，提出第三種適應(yīng)度函數(shù)f3(I)：

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

3 仿真結(jié)果分析

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

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

圖1 不同種群數(shù)量優(yōu)化值比較(適應(yīng)度函數(shù)1)

圖2 不同種群數(shù)量優(yōu)化值比較(適應(yīng)度函數(shù)2)

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

表1所示為兩種適應(yīng)度函數(shù)仿真結(jié)果比較，可見適應(yīng)度函數(shù)2可達(dá)的最高覆蓋率較高，適應(yīng)度函數(shù)1的收斂速度比適應(yīng)度函數(shù)2快，從整體性能來看，適應(yīng)度函數(shù)2性能較好。

表1 兩種適應(yīng)度函數(shù)比較

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

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

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

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

[4]周永華，李鵬，毛宗源.一種新的混合雜交方法及其在約束優(yōu)化中的應(yīng)用[J].計算機(jī)工程與應(yīng)用，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]張輪.一種無線傳感器網(wǎng)絡(luò)覆蓋的粒子群優(yōu)化方法[J].同濟(jì)大學(xué)學(xué)報(自然科學(xué)版)，2009，37(2)：262-266.

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

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

[9]YOUNIS O，F(xiàn)AHMY 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的無線傳感器網(wǎng)絡(luò)流量預(yù)測模型的研究[J].電子與信息學(xué)報，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.