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

劉　燕

（嘉應學院 電子信息工程學院，廣東　梅州　514015）

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

劉燕

（嘉應學院 電子信息工程學院，廣東梅州514015）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　仿真實驗

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

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

圖1　仿真實驗結(jié)果

4　結(jié)語

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

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

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

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

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

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

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

［7］李海龍，李寶華，韓彥春.無線傳感器網(wǎng)絡DV-Hop算法的一種優(yōu)化方法［J］.遼寧工程技術大學學報（自然科學版），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— ），女，湖南永州，碩士，助理實驗師；研究方向：控制科學與技術。