摘 要： 在無線傳感器網絡中，傳感器節點的分布通常具有隨機性和密集性，監測區域會出現覆蓋盲區或者覆蓋重疊。為此，推導出了無線傳感器最優覆蓋模型計算最少節點個數的公式，對遺傳算法中的適應度函數公式做了改進，將多重覆蓋率和覆蓋率的組合作為適應度函數。根據遺傳算法的相關內容和流程圖，利用遺傳算法對覆蓋策略做了仿真模擬，證明了所選用的方法的正確和優越性。
關鍵詞： 無線傳感器網絡；覆蓋；節點；遺傳算法
無線傳感器網絡WSN(Wireless Sensor Network)最早來源于軍事領域，1978年，卡內基—梅隆大學就在美國國防高級研究項目組(DARPA)的資助下成立了分布式傳感器網絡工作組，專門研究以WSN為基礎的軍事監視系統。該系統是傳感器技術、嵌入式計算技術、現代網絡及無線通信技術、分布式信息處理技術等的綜合應用。
遺傳算法[1]GA(Genetic Algorithm)是模擬達爾文的遺傳選擇和自然淘汰生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。該算法最早是1975年由美國Michigan大學HOLLAND J教授提出來的，它是一種基于自然選擇和群體遺傳機理的高度并行、隨機、自適應搜索算法。GA模擬了自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象，將每一個可能的解看作是群體中的一個個體，并將每一個個體編碼成字符串的形式，根據預定的目標函數對每個個體進行評價，給出一個適應值，利用遺傳算子選擇、交叉、變異等過程對這些個體進行組合，得到一群新個體。這一群新個體由于繼承了上一代的一些優良性狀，所以明顯優于上一代，這樣就逐步向著更優解的方向進化。
遺傳算法的主要優點[2]是從代表問題可能潛在解集的一個種群開始并行操作的，而不是從一個初始點開始尋優，在一定程度上避免了搜索過程收斂與局部最優解。其中一個種群則由經過基因編碼的一定數目的個體組成。初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解，在每一代根據問題域中個體的適應度大小挑選個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。
1 傳感器網絡最大覆蓋度的理想模型
2 最優部署模型節點數目公式
針對基于網格的WSN理想最優部署圖，要求解所使用的最少節點數目Ns，并不能簡單地利用矩形長邊的節點個數與寬邊的節點個數相乘的積得出。因為由圖可以看出，每列的節點并不是一一對齊的，而是錯落排列的。根據右邊界位置的不同，區域中每行節點的數目也不同。在右邊界選擇可以改變的情況下，每行節點的數目有時相同有時不同。在推導節點數目Ns時，要對右邊界位于不同位置的情況分別進行討論。在圖1的基礎上，為了便于對Ns進行推導，在原圖上增添了一些輔助線，作出求解最優模型節點數目的分析圖，如圖2所示。將各點坐標標注其上，底邊橫坐標從0開始，每隔
R依次標注。左邊界從R/2開始，每隔3R/2依次標注。把矩形各角依次標注字母A、B、C、D。
假設傳感器的感知半徑為R，被監測矩形區域的長為L，寬為W，節點的行數為Ws，每行節點的數目為Ls，所有節點的數目為Ns。由圖2可以看出，由底邊向上算起，作第2行圓的下切線一條輔助線l，則底邊到l的距離為:
3 基于遺傳算法的最優覆蓋策略
3.1 算法網絡模型
3.2 算法適應度函數的求解
在監測區域A的面積和傳感器的感知半徑一定的情況下，要使得節點數目最少且覆蓋度最大就是要使節點的分布盡量均勻，使得A內的多重覆蓋的區域最小。所謂多重覆蓋區域[4]就是區域被兩個或兩個以上的傳感器節點覆蓋(覆蓋重數≥2)。因此，問題就轉化為在一定的覆蓋度的前提下，如果能使重疊面積最小，才能使用最少的傳感器節點且分布更加均勻。將具有多重覆蓋區域的面積設為So，將m個活動節點的面積相加即為展開后的總面積，則可以寫作m×Asi=mπRs2。對于監測區域A有如下公式：
遺傳算法的適應度函數[5]尤為重要，它的選擇直接關系算法最后的仿真實驗結果的準確性，本模型統一由式(4)和式(5)兩個子函數構成，并分別加上一個權值w1、w2，保證w1+w2=1，具體值可以由網絡設計者針對網絡的需要來決定。
F=w1×f1+w2(1-f2) (6)
遺傳算法就是要使得適應度函數取最大值，而本文的目標是使多重覆蓋度越小越好。因此對于f2函數應該取相反值，可以得到(6)的適應度函數。本文對遺傳算法的適值函數F做了改進，由面積占有率的函數表達式組成，式(5)比用節點的利用率[5]表示能獲得更好的效果。
4 仿真實驗
本實驗采用MATLAB 7.0對遺傳算法求解最優覆蓋節點的方法進行仿真。
設監測區域為150×150的二維平面，傳感器的感知半徑R=15，初始群體隨機部署節點個數n=150，對于以上取值也滿足算法的要求，n遠大于上面所計算出的Ns的數值。基于遺傳算法進行求解，交叉概率一般在[0.4，0.99]中選取，因為在優化過程中，交叉概率太大容易破壞種群中的優良模式，太小雖然容易找到全局最優解但進化的速度太慢。變異概率選取一般是要求小于0.1。考慮以上原因，實驗選取交叉概率定為0.8，變異概率定為0.05，其目的就是既可以使節點最好的遺傳上一代的優秀節點又防止節點出現節點局部最優而使算法過早地收斂。根據遺傳算法的流程圖和以上實驗選取的參數因子，可以進行算法的仿真。實驗中對每運行100代的相關數據(包括覆蓋度、多重覆蓋度、活動節點的個數等信息)都做了數據記錄，圖3(a)、3(b)、3(c)、3(d)依次為算法初始狀態、100、200和300代時的仿真圖，圖中所顯示的節點均是處于活動狀態節點的分布情況。本文選取運行代數為300代時作為最后的最優部署圖。
有些遺傳算法[6]是采用了覆蓋度和節點利用率作為適應度函數，從而達到在滿足覆蓋度要求的前提下使節點數目最少的目的。本文利用覆蓋度和節點利用率作為適應度函數做了仿真實驗，在算法其他參數不變的前提下，將式(6)中以多重覆蓋率作為適應度函數改為節點利用率的函數，對實驗進行重新模擬，同樣將實驗運行到第300代，并記錄了與上面實驗同樣的相關數據信息，分別從覆蓋度和活動節點這兩個數目與上面的實驗做比較分析，可以得到圖3(e)和3(f)的比較圖。
從圖3(e)中可以看出，隨著代數的增加，選用覆蓋率和多重覆蓋率的組合作為適應度函數要比選用覆蓋率和節點利用率的組合作為適應度函數所得到的覆蓋度高。并且改進前的波形曲線有時有震蕩的現象，即得到的覆蓋度的結果會出現不穩定的現象。改進后的波形基本接近正態分布曲線，整個實驗過程很穩定，不會出現覆蓋度忽高忽低的現象。
從圖3(f)中可以看出，隨著代數的增加，選用覆蓋率和多重覆蓋率的組合作為適應度函數所用的節點數目要比選用覆蓋率和節點利用率的組合作為適應度函數的節點淘汰速度要快。并且到300代時，改進后的算法所用節點數目為47個，比改進前的算法所用節點數目58個要少，所以改進后的算法更加接近最優模型中節點的數目。由圖3(e)、3(f)可以看出，在整個實驗的過程中，改進后的算法的節點數目基本一直都小于改進前的節點的數目，即使實驗運行到某一代停止了，改進后的算法依然要明顯優越于改進前的算法。
本文改進的遺傳算法通過以上仿真實驗數據對覆蓋度和節點數目的比較，可以明顯地看出，本實驗選用的多重覆蓋度代替節點利用率作為適應度函數的遺傳算法是切實可行的。也達到了所要求的在滿足一定的覆蓋度的前提下，減少節點利用率的實驗目標。
參考文獻
[1] WARNEKE B， LAST M， LIEBOWITZ B. Smart dust: communicating with a cubic-millimeter computer[J]. IEEE Computer Magazine， 2001，34(1):44-51.
[2] CHONG Chee-Yee， KUMAR S P. Sensor Networks: Evolution[J]. Opportunities and Challenges Proceedings of the IEEE， 2003，9(8):1247-1256.
[3] SLIJEPCEVIC S， POTKONJAK M. Power efficient organization of wireless sensor networks[C]. In: Glisic S， ed. Proc. of the IEEE Conf.on Communications. Helsinki: IEEE Press，2001:472-476.
[4] ZHANG H， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Wireless Ad Hoc and Sensor Networks， 2005，1(1):89-124.
[5] 蔣杰，方力，張鶴穎，等.無線傳感器網絡最小連通覆蓋集問題求解算法[J].軟件學報，2006，17(2):175-184.
[6] 劉華峰，金士堯.三維無線傳感器網絡綜述[J].計算機應用，2007，27.