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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

適應(yīng)度用來(lái)度量個(gè)體在優(yōu)化計(jì)算中可能到達(dá)最優(yōu)解的優(yōu)良程度，個(gè)體的適應(yīng)度通過(guò)適應(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ù)在實(shí)際算法的應(yīng)用中存在收斂速度過(guò)快或過(guò)慢的問(wèn)題，容易收斂于局部最優(yōu)值，而不能準(zhǔn)確達(dá)到全局最優(yōu)解。下面對(duì)f1(I)進(jìn)行部分改進(jìn)，做線(xiàn)性變換得到f2(I)[8]：

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

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ù)增長(zhǎng)。

3 仿真結(jié)果分析

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

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

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

圖2 不同種群數(shù)量?jī)?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é)果比較，可見(jiàn)適應(yīng)度函數(shù)2可達(dá)的最高覆蓋率較高，適應(yīng)度函數(shù)1的收斂速度比適應(yīng)度函數(shù)2快，從整體性能來(lái)看，適應(yīng)度函數(shù)2性能較好。

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

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

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

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

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

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

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

[8]杜輝，肖德貴，羅娟，等.一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋度確定算法[J].計(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ú)線(xiàn)傳感器網(wǎng)絡(luò)流量預(yù)測(cè)模型的研究[J].電子與信息學(xué)報(bào)，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.