無(wú)線傳感網(wǎng)絡(luò)中基于覆蓋度優(yōu)化的自適應(yīng)遺傳算法*

王 騏，王青萍

(湖北第二師范學(xué)院 物理與機(jī)電工程學(xué)院，湖北 武漢 430205)

無(wú)線傳感網(wǎng)絡(luò)中基于覆蓋度優(yōu)化的自適應(yīng)遺傳算法*

王 騏，王青萍

(湖北第二師范學(xué)院 物理與機(jī)電工程學(xué)院，湖北 武漢 430205)

在資源受限、多跳的無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)分布或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不合理，將會(huì)產(chǎn)生感知陰影和覆蓋盲區(qū)，嚴(yán)重影響數(shù)據(jù)感知和網(wǎng)絡(luò)能效。為此提出一種基于節(jié)點(diǎn)移動(dòng)的總適應(yīng)度的遺傳算法，通過節(jié)點(diǎn)的移動(dòng)對(duì)節(jié)點(diǎn)進(jìn)行分簇和重定位，實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋度的優(yōu)化和高能效的節(jié)點(diǎn)動(dòng)態(tài)部署。仿真表明，算法對(duì)節(jié)點(diǎn)的重定位優(yōu)化了節(jié)點(diǎn)部署和路由配置，能量在各種不同功能性節(jié)點(diǎn)之間的分配更加合理，在適應(yīng)度參數(shù)保持平衡的情況下，減少了網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)“重分簇”的次數(shù)，最大限度地提高了網(wǎng)絡(luò)覆蓋度和生存期。

動(dòng)態(tài)部署；覆蓋度；能效；適應(yīng)度；遺傳算法；仿真

0 引言

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的分布以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的構(gòu)成，對(duì)于數(shù)據(jù)的感知和俘獲以及網(wǎng)絡(luò)的生存都具有十分重要的意義。在節(jié)點(diǎn)隨機(jī)部署的靜態(tài)傳感器網(wǎng)絡(luò)中，為了獲取良好的感知效果，在環(huán)境中往往會(huì)部署大于實(shí)際需要的冗余節(jié)點(diǎn)，因此網(wǎng)絡(luò)中有可能因?yàn)楣?jié)點(diǎn)分布的不合理，造成感知陰影和覆蓋盲區(qū)[1-2]，使得有些被監(jiān)測(cè)事件無(wú)法進(jìn)行及時(shí)跟蹤。特別是當(dāng)某個(gè)特定區(qū)域需要多個(gè)傳感器節(jié)點(diǎn)協(xié)同感知數(shù)據(jù)時(shí)，如果這個(gè)區(qū)域節(jié)點(diǎn)分布稀疏，那么就無(wú)法完成更精準(zhǔn)的測(cè)量。在能效方面，由于傳感器節(jié)點(diǎn)負(fù)載的分布高度不均，當(dāng)向匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳遞時(shí)，那些遠(yuǎn)離匯聚節(jié)點(diǎn)的傳感器節(jié)點(diǎn)將會(huì)消耗大量能量，從而導(dǎo)致資源迅速枯竭。另外，由于單跳或多跳網(wǎng)絡(luò)的跳長(zhǎng)固定不變，通信路徑無(wú)法優(yōu)化，不利于有效降低能耗。

相比于節(jié)點(diǎn)的靜態(tài)部署，基于節(jié)點(diǎn)移動(dòng)性的動(dòng)態(tài)部署能夠很好地解決上述問題。特別是在資源受限、多跳的移動(dòng)傳感器網(wǎng)絡(luò)中，可通過節(jié)點(diǎn)的移動(dòng)性構(gòu)建新的最短路徑，變多跳傳輸為少跳或單跳傳輸，從而縮短通信路徑，不僅可以均衡傳感器節(jié)點(diǎn)的負(fù)載分布，還可以最大限度減少通信開銷[3]。

本文基于對(duì)生物進(jìn)化機(jī)制的模仿，采用“進(jìn)化算法簇”中的遺傳算法(Genetic Algorithm，GA)，實(shí)現(xiàn)節(jié)點(diǎn)分布的動(dòng)態(tài)部署，進(jìn)一步優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋度，最大限度提高電池和傳感器節(jié)點(diǎn)的使用壽命。

1 遺傳算法適應(yīng)度函數(shù)的構(gòu)建

在網(wǎng)絡(luò)模型中按照功能將傳感器節(jié)點(diǎn)進(jìn)行了分類：(1)非活動(dòng)節(jié)點(diǎn)(斷電狀態(tài))；(2)簇頭(CH)；(3)簇間路由器(ICR)；(4)傳感器節(jié)點(diǎn)(NS)。遺傳算法的適應(yīng)度函數(shù)是用來判斷群體中個(gè)體的優(yōu)劣程度的指標(biāo)，它根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評(píng)估。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)直接影響到遺傳算法的性能，因此要結(jié)合求解問題本身的要求來定。本節(jié)將介紹移動(dòng)性的遺傳算法適應(yīng)度函數(shù)的構(gòu)建及其重要參數(shù)。

1.1 覆蓋均勻性適應(yīng)度

覆蓋均勻性適應(yīng)度(Coverage Uniformity Fitness，CUF)表示覆蓋度的變化情況及其對(duì)環(huán)境的適應(yīng)能力。節(jié)點(diǎn)的移動(dòng)可提高網(wǎng)絡(luò)覆蓋度，從而減小“覆蓋盲區(qū)”或增大監(jiān)測(cè)面積，這可通過重新調(diào)整簇內(nèi)成員節(jié)點(diǎn)之間的通信距離來實(shí)現(xiàn)。當(dāng)節(jié)點(diǎn)之間處于最佳距離時(shí)，相鄰節(jié)點(diǎn)間的最大距離以及所需的傳輸功率將趨于最小化，這有助于最大限度提高“節(jié)點(diǎn)通信適應(yīng)度NCF[4]”。CUF表示為：

(1)

其中M表示簇的數(shù)量，dj_min和dj_mean分別表示簇j內(nèi)節(jié)點(diǎn)間的最小通信距離和平均通信距離，ej_min和ej_mean分別表示簇j內(nèi)節(jié)點(diǎn)與簇頭間的最小通信距離和平均通信距離。

1.2 簇節(jié)點(diǎn)遷移適應(yīng)度

系統(tǒng)獎(jiǎng)勵(lì)傳感器節(jié)點(diǎn)在具有較低“簇頭適應(yīng)度CHF[4]”的簇頭之間進(jìn)行遷移，以此來改進(jìn)傳感器節(jié)點(diǎn)和簇頭分布的均勻性，這種均勻性的改進(jìn)用簇節(jié)點(diǎn)遷移適應(yīng)度(Cluster-Node Migration Fitness，CNMF)表示。簇節(jié)點(diǎn)遷移適應(yīng)度CNMF可表示為：

(2)

(3)

(4)

其中n表示第n個(gè)遷移對(duì)(源簇-目標(biāo)簇)，N表示遷移對(duì)的總數(shù)量，χns表示源簇內(nèi)冗余的傳感器節(jié)點(diǎn)數(shù)量，χnt表示目標(biāo)簇內(nèi)廢棄的傳感器節(jié)點(diǎn)數(shù)量，ρns和ρnt分別表示源簇和目標(biāo)簇內(nèi)簇頭下的節(jié)點(diǎn)數(shù)量，ρ表示每個(gè)簇的平均節(jié)點(diǎn)數(shù)，表示為：

(5)

從以上適應(yīng)度公式可看出，如果傳感器節(jié)點(diǎn)位于較低CHF的簇內(nèi)，且從源簇到目標(biāo)簇具有較高的擴(kuò)散梯度，那么這種情況有利于節(jié)點(diǎn)的遷移。

1.3 簇頭遷移適應(yīng)度

簇頭遷移適應(yīng)度(Cluster-Head Migration Fitness，CHMF)獎(jiǎng)勵(lì)簇頭(CH)和具有較低“路由器負(fù)載適應(yīng)度RLF[4]”的簇間路由器(ICR)的移動(dòng)。CH和ICR的移動(dòng)可獲得較高的RLF，這是因?yàn)椋?/p>

(1)ICR或CH的移動(dòng)可改變ICR的成員身份，從而優(yōu)化CH/ICR的數(shù)量[4]。

(2)通過移動(dòng)，ICR可與其他的功能性節(jié)點(diǎn)(簇頭和傳感器節(jié)點(diǎn))交換角色。比如通過交換，可以使具有較高電池容量的節(jié)點(diǎn)作為路由器使用，這有利于維護(hù)現(xiàn)有的拓?fù)浣Y(jié)構(gòu)。

簇頭遷移適應(yīng)度(CHMF)可表示為：

(6)

這里N表示移動(dòng)的節(jié)點(diǎn)總數(shù)，RLFn表示第n個(gè)節(jié)點(diǎn)的“路由器負(fù)載適應(yīng)度[4]”，BFnt表示非ICR節(jié)點(diǎn)的“電池適應(yīng)度[4]”，它與第n個(gè)ICR節(jié)點(diǎn)(電池適應(yīng)度為BFns)進(jìn)行交換形成交換對(duì)。ηn是布爾值，表示第n個(gè)ICR的交換對(duì)是否存在。顯然，根據(jù)式(6)可知，具有較低的電池容量和路由器負(fù)載適應(yīng)度的ICRs和CHs是易于進(jìn)行移動(dòng)的。

1.4 節(jié)點(diǎn)移動(dòng)適應(yīng)度

節(jié)點(diǎn)移動(dòng)的平均距離與它的移動(dòng)軌跡有關(guān)。由于節(jié)點(diǎn)的移動(dòng)會(huì)消耗電池的能量，因此在有限的能量范圍內(nèi)，節(jié)點(diǎn)移動(dòng)距離的期望值可看成是節(jié)點(diǎn)移動(dòng)所需能量的估計(jì)值。所以，要實(shí)現(xiàn)優(yōu)化覆蓋度和提高網(wǎng)絡(luò)能效的總體目標(biāo)，需要保持節(jié)點(diǎn)移動(dòng)特性的穩(wěn)定性，即節(jié)點(diǎn)移動(dòng)的頻率和幅度。

節(jié)點(diǎn)移動(dòng)適應(yīng)度(Node Motion Fitnes, NMF)可表示為：

NMF=(1-Fi(Q,distance)+(1-φi(n)))/2

(7)

其中φi(n)表示對(duì)第i個(gè)傳感器節(jié)點(diǎn)進(jìn)行懲罰的一種度量，原因是它移動(dòng)時(shí)位置不穩(wěn)定，到達(dá)同一個(gè)位置的次數(shù)達(dá)到n次(0≤φi(n)≤1)。Fi(·)表示第i個(gè)傳感器節(jié)點(diǎn)的懲罰函數(shù)，且0≤Fi(Q,NodeType)≤1，其中Q是電池的狀態(tài)，表示成一種量化步長(zhǎng)，distance表示節(jié)點(diǎn)移動(dòng)的預(yù)估距離，它是采用基于能量的定位方法，根據(jù)節(jié)點(diǎn)在不同位置的多個(gè)能量讀數(shù)間接估計(jì)出來的。

假定yi(t)表示第i個(gè)傳感器節(jié)點(diǎn)在時(shí)間間隔t內(nèi)的信號(hào)能量，則：

(8)

其中Gi表示第i個(gè)傳感器節(jié)點(diǎn)的增益因子，α(≈2)表示能量衰減因子，εi(t)表示參數(shù)建模誤差的累積效應(yīng)，S(t)表示目標(biāo)節(jié)點(diǎn)在時(shí)刻t釋放的能量，r(t)是D×1的向量，表示目標(biāo)節(jié)點(diǎn)在時(shí)刻t的坐標(biāo)，ri也是D×1的向量，表示第i個(gè)靜態(tài)傳感器節(jié)點(diǎn)的笛卡爾(直角)坐標(biāo)。

1.5 傳感器節(jié)點(diǎn)數(shù)據(jù)適應(yīng)度

傳感器節(jié)點(diǎn)數(shù)據(jù)適應(yīng)度(Sensor Data Fitness，SDF)衡量的是傳感數(shù)據(jù)的效率，并據(jù)此重新定位傳感器節(jié)點(diǎn)，使其數(shù)據(jù)傳輸能通過融合、消除或壓縮等方式被統(tǒng)一優(yōu)化。在給定信噪比(SNR)下，通過提高傳感質(zhì)量還可使數(shù)據(jù)傳輸進(jìn)一步優(yōu)化[5]。在資源(通信、電池等)受限情況下的最佳傳感質(zhì)量可表示為θ(B,F)，其中B表示與傳感操作相關(guān)的QoS條件，F(xiàn)表示定時(shí)策略。實(shí)施QoS屬性是為了充分利用可變數(shù)據(jù)的壓縮和融合規(guī)則，而實(shí)施定時(shí)策略是為了根據(jù)傳感器節(jié)點(diǎn)的不同情況(比如說密度等)來改變比特率[6]。一般來說，降低簇的平均能耗有利于傳感器的移動(dòng)。SDF表示為：

(9)

(10)

1.6 節(jié)點(diǎn)移動(dòng)的總適應(yīng)度

根據(jù)以上所述，節(jié)點(diǎn)移動(dòng)的總適應(yīng)度(Total Node Motion Fitness, TNMF)可表示為：

TNMF=α1CUF+α2CNMF+α3NMF+α4CHMF+α5SDF

(11)

其中α1+α2+α3+α4+α5=1，單個(gè)αi的權(quán)值可根據(jù)外部啟發(fā)式算法[7]進(jìn)行自適應(yīng)調(diào)整。算法根據(jù)節(jié)點(diǎn)的運(yùn)行情況在一定時(shí)間內(nèi)進(jìn)行多階段決策過程的優(yōu)化處理，以最大限度取得單個(gè)αi的最優(yōu)組合值為目標(biāo)。

2 節(jié)點(diǎn)部署遺傳算法

根據(jù)式(11)，采用GA遺傳算子，可設(shè)計(jì)出節(jié)點(diǎn)的最優(yōu)動(dòng)態(tài)部署算法。本節(jié)將介紹節(jié)點(diǎn)重定位的染色體表示，以及算法的主要流程。

2.1 染色體的表示

GA的染色體是解決目前問題的關(guān)鍵模塊，形式上與遺傳算子和適應(yīng)度函數(shù)相適應(yīng)[8]。染色體串由每個(gè)傳感器節(jié)點(diǎn)的移動(dòng)矢量形成，該矢量由7位二進(jìn)制數(shù)表示，稱為“基因”[9]，如圖1所示。

圖1 基于遺傳算法的節(jié)點(diǎn)重定位及其染色體表示

將染色體串的層次結(jié)構(gòu)定義成：

(3)只有當(dāng)其中一個(gè)x的值為1時(shí)，傳感器節(jié)點(diǎn)才會(huì)移動(dòng)。

在圖1中，根據(jù)節(jié)點(diǎn)坐標(biāo)的變化，節(jié)點(diǎn)1、2的位置改變了3次，節(jié)點(diǎn)3、4改變了2次，而節(jié)點(diǎn)5、6、9只改變1次，其他節(jié)點(diǎn)沒有改變。因此，每個(gè)節(jié)點(diǎn)重定位后的染色體表示為：

(9 0010001→0010001→0010001)、(10 0000000→0000000→0000000)。

2.2 算法的流程

算法的流程如圖2所示。

圖2 算法流程圖

產(chǎn)生初始種群時(shí)，初始染色體串一部分由隨機(jī)數(shù)發(fā)生器(RNG)產(chǎn)生，另一部分則由以前的種群樣本產(chǎn)生。每個(gè)染色體串根據(jù)TNMF函數(shù)(節(jié)點(diǎn)部署函數(shù))對(duì)適應(yīng)度進(jìn)行評(píng)估，參見式(11)。繁殖使得具有較高適應(yīng)度的染色體串能夠以較大概率產(chǎn)生下一代染色體子串。因此，根據(jù)TNMF定義的適應(yīng)度公式，具有最高TNMF值的染色體將更有機(jī)會(huì)繁殖下一代染色體子串。繁殖期間，算法采用“標(biāo)準(zhǔn)加權(quán)輪盤”的方式，選擇n個(gè)染色體串投入到“配對(duì)庫(kù)”中，以“交叉概率”產(chǎn)生N個(gè)染色體。染色體繁殖期間，多個(gè)交叉點(diǎn)的位置由隨機(jī)數(shù)發(fā)生器(RNG)計(jì)算產(chǎn)生。染色體變異時(shí)，將生成的N個(gè)染色體放入突變庫(kù)，突變算子根據(jù)自適應(yīng)突變概率(與平均適應(yīng)度成反比)使其產(chǎn)生突變，采用類似拋硬幣的方式來決定是否要將比特位進(jìn)行逆變處理(即0→1，1→0)。設(shè)突變概率的最大值為pm，則：

pg=pm(1-(N*TNMFavg)/TNMFtotal)

(12)

在選擇階段，根據(jù)適應(yīng)度值，從N+n個(gè)(n個(gè)雙親，N個(gè)孩子)染色體中選取n個(gè)染色體延續(xù)到下一代[10]。算法運(yùn)行時(shí)，比較每一次迭代得到的最優(yōu)適應(yīng)度，如果最大適應(yīng)度值和平均適應(yīng)度值變化不大、趨于穩(wěn)定，那么此適應(yīng)度值即為近似全局最優(yōu)解，算法終止，否則循環(huán)進(jìn)行。

3 算法仿真與結(jié)果分析

仿真的實(shí)驗(yàn)場(chǎng)景由100個(gè)節(jié)點(diǎn)組成，這些節(jié)點(diǎn)隨機(jī)分布在30×30的區(qū)間內(nèi)，每個(gè)節(jié)點(diǎn)具有唯一的UUID，隨機(jī)分配量化值介于0～15之間的電池容量，坐標(biāo)介于(0,0)～(30,30)之間。為簡(jiǎn)化起見，每個(gè)節(jié)點(diǎn)覆蓋的范圍為3×3，并假定節(jié)點(diǎn)之間的通信為視距傳播(即無(wú)線信號(hào)的直線傳播)[11]。一旦所有的節(jié)點(diǎn)都處于監(jiān)聽模式，那么GA運(yùn)行時(shí)的交叉率為60%，初始變異率為6%。式(11)中節(jié)點(diǎn)移動(dòng)的TNMF的單個(gè)αi組合值由外部啟發(fā)式算法運(yùn)行得到，α1～α5分別為：0.113 4、0.356 3、0.229 4、0.107 5、0.193 4。

實(shí)驗(yàn)?zāi)M匯聚節(jié)點(diǎn)的運(yùn)行，NS-2軟件模擬網(wǎng)絡(luò)的流量。盡管每個(gè)GA適應(yīng)度函數(shù)彼此存在競(jìng)爭(zhēng)，但它們收斂于系統(tǒng)的平衡點(diǎn)，從而最大限度提高了網(wǎng)絡(luò)生存期，獲得了網(wǎng)絡(luò)的最佳覆蓋度。節(jié)點(diǎn)靜態(tài)和動(dòng)態(tài)部署時(shí)，迭代次數(shù)與覆蓋度的函數(shù)關(guān)系如圖3所示。

圖3 節(jié)點(diǎn)靜態(tài)部署和動(dòng)態(tài)部署的第n次迭代與覆蓋度的函數(shù)關(guān)系

從圖3可以看出，在節(jié)點(diǎn)具有移動(dòng)性的動(dòng)態(tài)部署中，覆蓋度增加了大約30%。但由于節(jié)點(diǎn)具有移動(dòng)性，覆蓋度的增加也可能會(huì)導(dǎo)致通信開銷的增加，原因是：(1)對(duì)節(jié)點(diǎn)的移動(dòng)指令進(jìn)行加密和認(rèn)證；(2)節(jié)點(diǎn)的移動(dòng)可能會(huì)導(dǎo)致臨時(shí)數(shù)據(jù)包的丟失以及數(shù)據(jù)的損壞，從而引起通信路由上的安全認(rèn)證屬性進(jìn)一步增強(qiáng)。盡管節(jié)點(diǎn)重新部署會(huì)降低通信成本，但是節(jié)點(diǎn)的移動(dòng)會(huì)增加電池成本，因此可能會(huì)降低系統(tǒng)的總體效益。

圖4 節(jié)點(diǎn)靜態(tài)和動(dòng)態(tài)部署的第n次迭代與節(jié)點(diǎn)損失(電池的原因)百分率的函數(shù)關(guān)系

迭代次數(shù)與節(jié)點(diǎn)損失之間的關(guān)系如圖4所示。從此圖可以看出，動(dòng)態(tài)部署明顯優(yōu)于靜態(tài)部署，損失的節(jié)點(diǎn)數(shù)減少15%～20%。在靜態(tài)部署情況下，節(jié)點(diǎn)的損失呈指數(shù)級(jí)，而在動(dòng)態(tài)部署的情況下，由于總能量的分配更加優(yōu)化，節(jié)點(diǎn)在簇內(nèi)是逐漸消亡的。靜態(tài)部署方式下，節(jié)點(diǎn)的消亡會(huì)給覆蓋度帶來?yè)p失，由此會(huì)延長(zhǎng)數(shù)據(jù)傳輸?shù)穆窂剑黾訑?shù)據(jù)傳輸?shù)哪芎摹?/p>

4 結(jié)論

本文基于多目標(biāo)的遺傳算法，提出了一種移動(dòng)傳感器節(jié)點(diǎn)的動(dòng)態(tài)且高能效的部署方式。這種方式利用節(jié)點(diǎn)的移動(dòng)性，以最佳方式對(duì)傳感器節(jié)點(diǎn)進(jìn)行重新定位，從而進(jìn)一步優(yōu)化節(jié)點(diǎn)的分配、路由配置，進(jìn)而最大限度提高網(wǎng)絡(luò)覆蓋度和生存期。在實(shí)驗(yàn)中可以觀測(cè)到，由于節(jié)點(diǎn)的重定位提高了電池利用率(適應(yīng)度)，因此能量在各種不同功能性節(jié)點(diǎn)之間的分配更加合理。在適應(yīng)度參數(shù)保持平衡的情況下，節(jié)點(diǎn)位置的改變會(huì)導(dǎo)致節(jié)點(diǎn)功能的改變，這也會(huì)減少網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)“重分簇”的次數(shù)。

[1] 付華,韓爽.基于新量子遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)感知節(jié)點(diǎn)的分布優(yōu)化[J]. 傳感技術(shù)學(xué)報(bào),2008,21(7): 1259-1263.

[2] 陳喻,王飛宇,楊任爾,等.利用sink的移動(dòng)性提高無(wú)線傳感器網(wǎng)絡(luò)壽命[J].機(jī)電工程, 2013,30(5):636-640.

[3] 黃月,項(xiàng)妹,肖磊,等. 無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)部署問題研究[J]. 控制工程,2012,19(4):648-649.

[4] KHANNA R, Liu Huaping， CHEN H H. Self-organization of sensor networks using genetic algorithms[C]. IEEE International Conference on Communication, Istanbul, 2006：3377-3382.

[5] 張石,鮑喜榮,陳劍,等. 無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)的分布優(yōu)化問題[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007,28(4):489-492.

[6] 唐明虎，張長(zhǎng)宏，昝風(fēng)彪. 無(wú)線傳感器網(wǎng)絡(luò)APIT定位算法[J]. 微型機(jī)與應(yīng)用，2010,29(21):1-4.

[7] 班冬松,溫俊,蔣杰,等. 移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)k-柵欄覆蓋構(gòu)建算法[J]. 軟件學(xué)報(bào), 2011,22(9): 2089-2103.

[8] 何璇, 郝群, 宋勇. 一種移動(dòng)無(wú)線視頻傳感器節(jié)點(diǎn)的覆蓋算法[J]. 傳感技術(shù)學(xué)報(bào), 2009, 22(8):1163-1168.

[9] 葉苗,王宇平，代才，等. 無(wú)線傳感器網(wǎng)絡(luò)中新的最小暴露路徑問題及其求解算法[J]. 通信學(xué)報(bào)，2016,37(1):49-60.

[10] 丁凡，周永明. 移動(dòng)性無(wú)線傳感器網(wǎng)絡(luò)吞吐量跨層優(yōu)化[J]. 電子技術(shù)應(yīng)用, 2013,39(2):100-102.

[11] 王璨，駱堅(jiān)，張大方，等. 一種基于移動(dòng)性的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].計(jì)算機(jī)工程與科學(xué),2012,34(3):6-12.

An adaptive genetic algorithm based on coverage optimization in wireless sensor metworks

Wang Qi, Wang Qingping

(College of Physics and Electromechanical Engineering, Hubei University of Education, Wuhan 430205, China)

In resource-constrained and multi-hop wireless sensor networks, unreasonable nodes distribution or network topology will bring about the sensing shadow and coverage holes, which will badly affect data sensing and energy efficiency of the network. According to the total fitness associated with node movement, a genetic algorithm based on node mobility was proposed, which divided all nodes into clusters and relocated them to achieve the optimization of coverage and dynamic deployment of nodes with high energy efficiency. Simulation experiments showed that this approach optimally relocated sensor nodes, further optimized node deployment and route assignment, which made a better distribution of energy among various functional nodes, also reduced frequent re-clustering by just exchanging the positions while maintaining fitness parameters in equilibrium, thus maximized coverage and network lifetime.

dynamic deployment; coverage; energy efficiency; fitness; genetic algorithm; simulation

湖北省高等學(xué)校優(yōu)秀中青年科技創(chuàng)新團(tuán)隊(duì)計(jì)劃項(xiàng)目(T201417)

TN918.91

A

10.19358/j.issn.1674- 7720.2017.08.003

王騏，王青萍.基于覆蓋度優(yōu)化的自適應(yīng)遺傳算法[J].微型機(jī)與應(yīng)用，2017,36(8)：7-10，14.

2016-11-21)

王騏(1970-)，男，博士，副教授，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)安全、嵌入式系統(tǒng)應(yīng)用。

王青萍(1980-)，女，博士，副教授，主要研究方向：光電功能材料與器件。

________________________