劉　燕

（嘉應(yīng)學(xué)院 電子信息工程學(xué)院，廣東　梅州　514015）

基于遺傳算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化方法研究

劉燕

（嘉應(yīng)學(xué)院 電子信息工程學(xué)院，廣東梅州514015）

隨著科技的不斷發(fā)展，傳感器網(wǎng)絡(luò)得到了極大的發(fā)展，其擁有極為廣闊的應(yīng)用前景，已被應(yīng)用于智能家居、空間探索、軍事、健康護(hù)理以及環(huán)境監(jiān)測(cè)等領(lǐng)域。文章就其測(cè)控系統(tǒng)所具有的特殊性，提出了一種可以達(dá)到節(jié)點(diǎn)連通約束來(lái)對(duì)節(jié)點(diǎn)數(shù)量加以減少的新模型，同時(shí)利用遺傳算法對(duì)其加以?xún)?yōu)化計(jì)算。要想使節(jié)點(diǎn)收斂速度大幅提升，文章將采取以二分法為基礎(chǔ)的遺傳算法進(jìn)行研究。

遺傳算法；無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)優(yōu)化；連通性

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是一種由眾多小型傳感器所構(gòu)成的網(wǎng)絡(luò)，其主要的功能是對(duì)網(wǎng)絡(luò)區(qū)域中的對(duì)象信息以協(xié)作式進(jìn)行感知、采集并進(jìn)行處理，之后將其發(fā)送至基站中。隨著對(duì)WSN不斷深入的研究以及廣泛應(yīng)用，WSN將被應(yīng)用到人類(lèi)的生活生產(chǎn)的各個(gè)領(lǐng)域。傳感器網(wǎng)絡(luò)在之前主要有兩類(lèi)分布方式，即隨機(jī)撒布和有計(jì)劃安置。但是其具有各自的應(yīng)用方面以及優(yōu)勢(shì)，因此在進(jìn)行具體應(yīng)用時(shí)要根據(jù)具體情況加以選取。本文的WSN僅需進(jìn)行特定地點(diǎn)展開(kāi)監(jiān)測(cè)，所以分布范圍廣、節(jié)點(diǎn)相對(duì)較少。路由器節(jié)點(diǎn)具有較為靈活的位置，同時(shí)該節(jié)點(diǎn)還具有一定的移動(dòng)性。

1　優(yōu)化數(shù)學(xué)模型

定義：擁有傳感器節(jié)點(diǎn)集合，g =｛C1， C2， …CN｝，求取一個(gè)子集從而實(shí)現(xiàn)將C?g，整個(gè)網(wǎng)絡(luò)進(jìn)行連通，同時(shí)滿(mǎn)足C中節(jié)點(diǎn)數(shù)最少。

假設(shè)監(jiān)測(cè)區(qū)域是二維平面：其｛ S（x ， y ）： 0 ≤ x ≤Length 0 ≤ x ≤ Width ｝中Length是檢測(cè)區(qū)的長(zhǎng)度，Width是監(jiān)測(cè)區(qū)的寬度；所安置的感知節(jié)點(diǎn)數(shù)是N個(gè)，而且已知全部節(jié)點(diǎn)坐標(biāo)；根據(jù)區(qū)域大小和節(jié)點(diǎn)數(shù)估計(jì)移動(dòng)節(jié)點(diǎn)數(shù)為M個(gè)，從而確保該網(wǎng)絡(luò)連通性，移動(dòng)節(jié)點(diǎn)坐標(biāo)為（x，y）；節(jié)點(diǎn)i，j間存在的距離為dij；網(wǎng)絡(luò)內(nèi)全部節(jié)點(diǎn)擁有同等傳輸范圍，其傳輸范圍是以（x，y）坐標(biāo)作為圓心，半徑是r的圓；將全部節(jié)點(diǎn)看作是一個(gè)無(wú)向圖，其鄰接矩陣為A，若dij< r時(shí)，節(jié)點(diǎn)能夠直接通信，此時(shí)稱(chēng)i，j間有一條弧，相應(yīng)的Aij是1［1］。

假定圖G具有n個(gè)頂點(diǎn)，其鄰接矩陣是A，那么道路矩陣可以根據(jù)鄰接矩陣A通過(guò)布爾運(yùn)算加以獲取：

利用遺傳算法展開(kāi)優(yōu)化計(jì)算過(guò)程中，通常編碼長(zhǎng)度是固定的，而其中固定節(jié)點(diǎn)數(shù)目已知，也就是說(shuō)要移動(dòng)節(jié)點(diǎn)數(shù)量確定。所以，優(yōu)化過(guò)程中應(yīng)該采取數(shù)量相對(duì)較多的節(jié)點(diǎn)，一旦節(jié)點(diǎn)有冗余式，一定會(huì)產(chǎn)生重復(fù)位置的節(jié)點(diǎn)，那么可以將重合節(jié)點(diǎn)看作成一個(gè)節(jié)點(diǎn)，這邊可以將節(jié)點(diǎn)數(shù)目最小化加以轉(zhuǎn)化，利用重復(fù)節(jié)點(diǎn)最多化來(lái)進(jìn)行間接求?。?］。那么優(yōu)化函數(shù)便是：

根據(jù)上述函數(shù)中未將重合結(jié)點(diǎn)數(shù)當(dāng)作是變量，主要是確保指標(biāo)可以滿(mǎn)足連續(xù)性，這樣可以將重合節(jié)點(diǎn)數(shù)較少的染色體進(jìn)行優(yōu)化計(jì)算。函數(shù)中的bD是距離基值，其作用是判斷節(jié)點(diǎn)間的重合程度。若dij越小那么函數(shù)值將會(huì)越大，重合程度就越高。bD值越小，則重合判斷的越精細(xì)。bM+N是重合節(jié)點(diǎn)數(shù)目基值，該值是由檢測(cè)區(qū)域與節(jié)點(diǎn)數(shù)目決定的［3］。

而對(duì)于連通約束，則將采取懲罰函數(shù)，定義懲罰函數(shù)是：

式中，PMN是道路矩陣P內(nèi)不是0的元素?cái)?shù)目；bMN是一個(gè)基值，其值是由（M+N）2加以對(duì)其決定的。若網(wǎng)絡(luò)內(nèi)全部節(jié)點(diǎn)均可以利用多跳路由與其他節(jié)點(diǎn)進(jìn)行連通時(shí)，那么PMN=（M+N）2，那么上述函數(shù)其值最大是1，從而可以確保整個(gè)網(wǎng)絡(luò)所具有的連通性。

利用上述函數(shù)進(jìn)行相應(yīng)的優(yōu)化，之前計(jì)算出的移動(dòng)節(jié)點(diǎn)數(shù)N與優(yōu)化重合節(jié)點(diǎn)數(shù)相減得到的數(shù)目就是實(shí)際所需安裝的路由節(jié)點(diǎn)數(shù)。

2　基于GA節(jié)點(diǎn)分布優(yōu)化

遺傳算法即GA是一類(lèi)創(chuàng)建于自然選擇原理以及自然遺傳機(jī)制前提下的迭代自適應(yīng)檢索方式［4］。在進(jìn)行最優(yōu)解求取過(guò)程中，要從隨機(jī)解開(kāi)始，該隨機(jī)解被稱(chēng)作種群，種群內(nèi)的所有解均是一個(gè)個(gè)體［5］。其中個(gè)體解利用適值加以評(píng)定來(lái)選取相應(yīng)最佳解，適值好的個(gè)體擁有的生存幾率會(huì)相對(duì)較高［6］。

此外，還應(yīng)對(duì)適應(yīng)度進(jìn)行一定的選取。通過(guò)對(duì)上文的探討后，WSN的分布優(yōu)化作為多目標(biāo)優(yōu)化工作，應(yīng)該使節(jié)點(diǎn)數(shù)和其連通性能夠達(dá)到一種平衡?？偰繕?biāo)函數(shù)即是上文提到的兩函數(shù)經(jīng)過(guò)歸一化得到的加權(quán)和。將總適應(yīng)度函數(shù)做出如下定義：

其中，α1是優(yōu)化函數(shù)的加權(quán)值，α2是懲罰函數(shù)的加權(quán)值，其選取范圍取決于該網(wǎng)絡(luò)指標(biāo)所需的綜合要求，同時(shí)要滿(mǎn)足的是

3　仿真實(shí)驗(yàn)

這里利用仿真實(shí)驗(yàn)進(jìn)行算法有效性的檢驗(yàn)。對(duì)安裝在400m×600m監(jiān)測(cè)區(qū)域中的10個(gè)節(jié)點(diǎn)加以仿真分布。根據(jù)算法要求事先安裝10個(gè)固定節(jié)點(diǎn)，同時(shí)將每個(gè)節(jié)點(diǎn)的傳輸半徑設(shè)置為120m，種群個(gè)體數(shù)量是200，其變異概率是0.02；交叉概率是0.5。仿真結(jié)果如圖1所示。

通過(guò)對(duì)圖1進(jìn)行分析，在初始化過(guò)程中，節(jié)點(diǎn)存在極少的連通，整個(gè)檢測(cè)網(wǎng)絡(luò)完全是不連通狀態(tài)。隨著優(yōu)化代數(shù)不斷地向前推進(jìn)，相互連通的節(jié)點(diǎn)數(shù)也在不斷地增加，當(dāng)運(yùn)行至90代時(shí)，全部節(jié)點(diǎn)均已連通，同時(shí)存在一個(gè)移動(dòng)節(jié)點(diǎn)與其他節(jié)點(diǎn)發(fā)生重合。當(dāng)運(yùn)行至第100代時(shí)，其結(jié)果與第90代結(jié)果基本一致，這就說(shuō)明此時(shí)已經(jīng)得到了節(jié)點(diǎn)分布的最好方案。此方案分布不但確保了全部固定節(jié)點(diǎn)得到了連通，而移動(dòng)節(jié)點(diǎn)也得到了一定的優(yōu)化。而且還有一個(gè)節(jié)點(diǎn)發(fā)生重合，這就說(shuō)明安裝9個(gè)節(jié)點(diǎn)便能確保網(wǎng)絡(luò)的連通性。

圖1　仿真實(shí)驗(yàn)結(jié)果

4　結(jié)語(yǔ)

綜上所述，通過(guò)對(duì)無(wú)線(xiàn)傳感進(jìn)行一定研究，在確保固定節(jié)點(diǎn)所具有的連通性基礎(chǔ)上，盡可能對(duì)移動(dòng)節(jié)點(diǎn)加以減少。根據(jù)對(duì)二分法為基礎(chǔ)的遺傳算法進(jìn)行仿真，可以實(shí)現(xiàn)對(duì)染色體長(zhǎng)度進(jìn)行極大地縮減，從而使收斂速度得到快速提升，在全部節(jié)點(diǎn)連通的基礎(chǔ)上將節(jié)點(diǎn)減少。

［1］葉苗，王宇平.一種新的容忍惡意節(jié)點(diǎn)攻擊的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)安全定位方法［J］.計(jì)算機(jī)學(xué)報(bào)，2013（3）：532-545.

［2］沈海洋.基于遺傳PSO的無(wú)線(xiàn)傳感網(wǎng)絡(luò)覆蓋優(yōu)化算法研究［J］.微電子學(xué)與計(jì)算機(jī)，2013（3）：148-151.

［3］胡靜嫻，馮秀芳.RGA-D：一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法［J］.測(cè)控技術(shù)，2014（10）：105-108.

［4］樊富有，楊國(guó)武，樂(lè)千榿，等.基于量子遺傳算法的無(wú)線(xiàn)視頻傳感網(wǎng)絡(luò)優(yōu)化覆蓋算法［J］.通信學(xué)報(bào)，2015（6）：98-108.

［5］邵開(kāi)麗，付輝.能耗均衡的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多Sink節(jié)點(diǎn)部署優(yōu)化方法［J］.儀表技術(shù)與傳感器，2015（9）：106-110.

［6］沙超，王汝傳，黃海平，等.一種基于多目標(biāo)遺傳優(yōu)化的無(wú)線(xiàn)多媒體傳感器網(wǎng)絡(luò)節(jié)能覆蓋方法［J］.電子學(xué)報(bào)，2012（1）：19-26.

［7］李海龍，李寶華，韓彥春.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)DV-Hop算法的一種優(yōu)化方法［J］.遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2016（5）：523-528.

Research on optimization method of wireless sensor network node based on genetic algorithm

Liu Yan
（Electronic and Information Engineering Department of Jiaying University， Meizhou 514015， China）

With the continuous development of science and technology， the sensor network has been developed greatly， which has a very broad application prospects， and has been applied to smart home， space exploration， military， health care and environmental monitoring and other felds. A new model which can reduce the number of nodes in the control system is proposed in this paper， which can be achieved by using the genetic algorithm to optimize the measurement system. In order to improve the convergence speed of the nodes， this paper will adopt the genetic algorithm based on the dichotomy to carry out the research.

genetic algorithm； wireless sensor network； node optimization； connectivity

劉燕（1989— ），女，湖南永州，碩士，助理實(shí)驗(yàn)師；研究方向：控制科學(xué)與技術(shù)。