傅霞玲陳江勇許力殷知越

（1.福建師范大學數(shù)學與計算機科學學院，福建福州350007；2.福建省德化陶瓷職業(yè)技術學院，福建泉州362500）

1.引言

隨著通信技術、嵌入式技術、傳感器技術、無線技術的迅速發(fā)展和日趨成熟，具有通信能力、計算能力和感知能力的微型傳感器節(jié)點開始在世界范圍內(nèi)涌現(xiàn)。數(shù)目眾多的傳感器節(jié)點，以Ad Hoc方式構成無線傳感器網(wǎng)絡[1]。無線傳感器網(wǎng)絡的傳感器節(jié)點，隨機撒播或均勻有規(guī)則地分布在監(jiān)測區(qū)域，協(xié)同感知、采集和處理網(wǎng)絡覆蓋范圍內(nèi)的感知對象的信息，并把收集的信息，以多跳的方式發(fā)送給匯集節(jié)點（Sink節(jié)點）。但由于傳感器節(jié)點由電池供電，電池的容量一般不大，而且其特別的應用領域也決定傳感器在使用過程中，很難再充電或更換。因此，節(jié)能以延長網(wǎng)絡的生命周期是無線傳感器網(wǎng)絡設計的首要任務[2-3]。

l929年，匈牙利作家F.Karinthy最早提出了“小世界現(xiàn)象”的論斷[4]。1998年，Watts和Strogatz對規(guī)則網(wǎng)絡進行斷鏈重連得到了既具有小世界效應(L～lnN)，又具有集團化特征的網(wǎng)絡，提出了著名的W-S小世界網(wǎng)絡(Small World Network SWN)這一概念，并建立了模型[5]。2004年，Helmy等學者通過在Ad Hoc網(wǎng)絡中引入邏輯鏈路形成具有小世界效應的無線網(wǎng)絡，驗證了小世界網(wǎng)絡同樣適用于具有空間屬性的無線網(wǎng)絡[6]。Helmy等人還研究了在磁盤網(wǎng)絡模型中以靜態(tài)匯聚節(jié)點為中心的無線傳感器網(wǎng)絡中設置有線鏈路產(chǎn)生捷徑的能量效率問題[7]。

但是，Helmy等人只是分析了有線的最優(yōu)長度、加入多少的有線后能量效率達到最高，以及最大可以達到的能量節(jié)省率，而沒有分析這些有線放置的最優(yōu)位置。因此，本文采用遺傳算法，研究在磁盤網(wǎng)絡模型中，傳感器節(jié)點均勻分布的單個Sink節(jié)點的靜態(tài)異構傳感器網(wǎng)絡中有線捷徑的優(yōu)化部署問題。通過有線捷徑的引入，最大幅度地降低平均路徑長度，達到提高網(wǎng)絡能量效率、延長網(wǎng)絡生命周期的目的。

2.網(wǎng)絡模型及路由策略

2.1 網(wǎng)絡模型

本文采用磁盤網(wǎng)絡模型，傳感器節(jié)點以圖1所示的方式均勻分布于網(wǎng)絡拓撲中，節(jié)點之間信息傳輸采用曼哈頓距離（Manhattan Distance），每個節(jié)點到鄰居節(jié)點的距離均為一跳。網(wǎng)絡中只有一個Sink節(jié)點，所有的普通節(jié)點都把采集的信息發(fā)送到Sink節(jié)點。網(wǎng)絡為靜態(tài)及位置相關，即當網(wǎng)絡布設完成后，節(jié)點將保持位置不變。

在網(wǎng)絡中加入有線捷徑（wired shortcuts）或中繼節(jié)點，構造具有“小世界效應”的異構傳感器網(wǎng)絡。有線捷徑一端放置在遠離Sink節(jié)點的地方，另一端與Sink節(jié)點只有一跳的距離、與Sink節(jié)點可以直接通信?；蛘咭部梢圆捎镁哂凶銐虻哪芰抗⒋鎯吞幚砟芰Ω鼜姷闹欣^節(jié)點，這些中繼節(jié)點也是與Sink節(jié)點只有一跳的距離。兩種情況下，都只要確定遠離Sink節(jié)點的那一端的位置，分析的情況是一樣的，因此，在本文的論述中，捷徑與中繼節(jié)點為同義詞。

在圖1的磁盤網(wǎng)絡模型中，從拓撲的中心往外看，共有5個圓，表示一個具有5層的磁盤網(wǎng)絡。中心的第一個圓為第1層，從中心往外看，每個圓環(huán)分別為第2、3、4、5層。若Sink節(jié)點在拓撲中心上，則每一層上的節(jié)點，不管是在圓上，還是在該層的圓環(huán)內(nèi)，到Sink節(jié)點的跳數(shù)是一樣的（采用貪婪路由策略）。

圖1 節(jié)點均勻分布的5層磁盤網(wǎng)絡模型（用θ=60o的斜坐標系表示）

2.2 路由策略

本文采用貪婪路由策略，即某個節(jié)點N要發(fā)送數(shù)據(jù)到Sink節(jié)點時，它把數(shù)據(jù)包發(fā)送給距離Sink最近的鄰居節(jié)點，鄰居節(jié)點再重復這種過程，直到數(shù)據(jù)包發(fā)送到Sink節(jié)點。采用貪婪路由算法，數(shù)據(jù)包以最小的跳數(shù)，就可以到達Sink節(jié)點。當網(wǎng)絡中加入有線捷徑時，顯然，對于有些節(jié)點，通過有線捷徑構成的有線鏈路，可以更快地到達Sink節(jié)點，因此，信息通過有線鏈路，傳輸?shù)絊ink節(jié)點；而對于另一些節(jié)點，直接通過無線鏈路，傳輸距離更近，就不必要通過有線鏈路了。數(shù)據(jù)包到底如何傳輸，需要進行比較判斷：

設：用NS（xs，ys）表示Sink節(jié)點坐標，Ni(i，j）表示普通節(jié)點坐標，Nn(xn，yn)為中繼節(jié)點坐標。

令：dWSN=|i-xs|+|j-ys|，dHSN=|i-xn|+|j-yn|+1

其中，dWSN表示普通節(jié)點通過無線鏈路到達Sink節(jié)點的距離（跳數(shù)）；dHSN表示通過有線鏈路到達Sink節(jié)點的距離（跳數(shù)）。

若：dWSN＜dHSN，則數(shù)據(jù)包通過無線鏈路到達匯集節(jié)點；否則，數(shù)據(jù)包通過有線鏈路到匯集節(jié)點。

3.“捷徑”的優(yōu)化部署及性能指標

3.1 “捷徑”的優(yōu)化部署

傳感器網(wǎng)絡中節(jié)點的能量消耗主要在于數(shù)據(jù)包的傳送和接收過程，整個網(wǎng)絡的能耗與網(wǎng)絡中所有節(jié)點達到Sink節(jié)點的總跳數(shù)成正比。因此，我們可以在網(wǎng)絡的平均路徑長度和網(wǎng)絡的能耗之間建立對應關系。網(wǎng)絡的平均路徑長度最小，也即能耗最小。

用L(N)表示在m層磁盤網(wǎng)絡模型中，放置n個中繼節(jié)點后異構傳感器網(wǎng)絡的平均路徑長度。則L(N)為：

其中：

(i，j)為網(wǎng)絡中任一普通節(jié)點的坐標

(x1…n，y1…n)為中繼節(jié)點的坐標

(xs，ys)為sink節(jié)點的坐標

由于網(wǎng)絡中第一層為6個節(jié)點，其余各層的節(jié)點數(shù)構成公差為6的等差數(shù)列，因此，m層磁盤網(wǎng)絡的總節(jié)點數(shù)為：Sm=a1*m+m(m-1)d/2=6m+m(m-1)*6/2=3m2+3m

3.2 網(wǎng)絡性能評價指標

用L(O)表示未加線時無線傳感網(wǎng)絡的平均路徑長度，用ESR（Energy Saving Raito）表示加線后網(wǎng)絡的能量節(jié)省率，則：

由式(3)可知，在網(wǎng)絡規(guī)模及有線條數(shù)確定的情況下，L(O)為一固定值，因此，若要提高網(wǎng)絡的能量效率，獲得最大的能量節(jié)省率ESR，必須是有線得到優(yōu)化放置，使得L(N)為最小值?？梢姡肊SR可以很方便地評價網(wǎng)絡的性能指標。

4.用遺傳算法實現(xiàn)“捷徑”的優(yōu)化部署

4.1 遺傳算法

遺傳算法是一種模擬自然進化過程發(fā)展起來的高度并行、隨機、自適應的搜索算法。它從代表問題可能的解集的一個種群開始，而一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群[8，9]。

本文采用輪盤賭選擇方案，即每個個體串按照它們的適應值進行選擇，選擇操作通過隨機方法來實現(xiàn)。變異也是產(chǎn)生新個體的一種方法，但一般變異概率都非常小，故不是產(chǎn)生新個體的主要方法。通過變異操作可以改變遺傳算法的局部搜索能力。

4.2 編碼模式及初始種群的產(chǎn)生

本文采用了一種編碼映射方法：把所有的節(jié)點按坐標從0開始進行編號。對于半徑為5的磁盤網(wǎng)絡，坐標為(5，0)的節(jié)點對應編號0，(5，1)對應編號1，依次類推。所以，半徑為m的磁盤網(wǎng)絡的所有節(jié)點對應一個整數(shù)集合Zn={0，1，2，3……，3m2+3m}，這樣部署n個中繼節(jié)點的一個方案就唯一對應Zn的一個包含n個元素的子集，即每個染色體對應Zn的一個包含n個元素的子集。并且，我們在開始的時候隨機產(chǎn)生一定數(shù)目的Zn的n元子集作為初始種群。

4.3 適應度函數(shù)

對生存環(huán)境較高的物種將獲得更多的繁殖機會，因此適應度值和目標函數(shù)值成反比關系，目標函數(shù)值越小的個體，其適應度函數(shù)值越大，保證以較大的概率被選擇交叉產(chǎn)生下一代，適應度函數(shù)定義如(4)式所示。

公式中，考慮到取倒數(shù)后，值太小，所以用1/L(N)乘以一個系數(shù)（3m2+3m），并且再取平方值以拉大各數(shù)值間的差距。

5.仿真實驗及分析

5.1 仿真環(huán)境

實驗考慮Sink節(jié)點位于最外層第5層圓環(huán)上這種較特殊的情況，坐標為S(5，0)。用Visual C++6.0實現(xiàn)仿真，仿真實驗數(shù)據(jù)如下所示。

網(wǎng)絡層數(shù)M取值：5-20

中繼節(jié)點個數(shù)N取值：0，1，2…10，15，…50

種群大?。?0

交叉概率：0.80

變異概率：0.05

遺傳總代數(shù)：1000

隨機數(shù)種子：88

算法重復執(zhí)行次數(shù)：5

5.2 仿真結果及分析

5.2.1 中繼節(jié)點的位置確定且不是唯一解

表1 兩種網(wǎng)絡規(guī)模下中繼節(jié)點優(yōu)化部署方案

由表1可知，中繼節(jié)點的坐標可以獲得，因此，采用本方案可以直接確定中繼節(jié)點的位置，對中繼節(jié)點可以直接進行部署，并且由于對稱性等原因，優(yōu)化部署方案不是唯一解。

5.2.2 平均路徑長度與中繼節(jié)點的關系

圖2 不同網(wǎng)絡規(guī)模下平均路徑長度與中繼節(jié)點的關系

在圖2中，網(wǎng)絡規(guī)模m增大時，若不加捷徑，平均路徑長度急劇增大，如圖所示，m=5，L(0)=7.7；m=20，L(0)=35.5。但當加入少量的有線后(1-4)，平均路徑長度急劇下降，當捷徑增加到10時，各種網(wǎng)絡規(guī)模下的平均路徑長度相差不大，說明隨著捷徑的加入使得平均路徑長度大大減小，網(wǎng)絡的能耗大大降低。隨著有線數(shù)量的增加，平均路徑長度減小緩慢。這也從另一方面說明，并不是增加越多的有線越好。到底要加多少的有線，既可以較大幅度的降低能耗，又可以兼顧經(jīng)濟效益，這需要在兩者之間進行權衡。

5.2.3 能量節(jié)省率與中繼節(jié)點個數(shù)的關系

由圖3得，當中繼節(jié)點個數(shù)增加到10個時，網(wǎng)絡的能量節(jié)省率可以達到70-80%；繼續(xù)增加中繼節(jié)點個數(shù)到25，能量節(jié)省率達到77-87%。這與Helmy等人在論文[7]中的結論“加線5-24，路徑長度減少60-70%”相比，采用此方案可以獲得更高的能量節(jié)省率。

圖3 不同網(wǎng)絡規(guī)模下能量節(jié)省率與中繼節(jié)點個數(shù)之間的關系

6.結論

本文研究磁盤網(wǎng)絡模型的節(jié)點均勻分布的異構傳感器網(wǎng)絡的捷徑優(yōu)化部署問題。理論分析與仿真實驗表明，采用遺傳算法可以得到優(yōu)化部署方案，通過最大限度減少網(wǎng)絡的平均路徑長度，獲得最大的能量節(jié)省率，從而達到延長網(wǎng)絡的生命周期的目的。并且有線的條數(shù)和位置確定后，線的長度也即確定，因此，便于網(wǎng)絡的布設與管理。

[1]Estrin D，Govindan R，Heidemann J，et a1.Next centurychal1enges：scalable coordinate in sensor network[A].In：Proc.of 5th ACM／IEEEInt’1Confon Mobile Computing and Networking[C].Washington，USA：ACM Press，1999.263～270.

[2]孫利民，李建中，陳渝，無線傳感器網(wǎng)絡[M].北京：清華大學出版社，2005.

[3]周賢偉，覃伯平，徐福華，無線傳感器網(wǎng)絡與安全[M].國防工業(yè)出版社，2007.

[4]Braun T.Hungarian priority in network theoty[M].Science，2004.

[5]WATTS D，STROGATZ S.Collective dynamics of‘small-world’networks[J].Nature，1998，393：440—442.

[6]HELMY A.Contact based architecture for resourcediscovery(CARD)in large scale MANets[J].IEEE／ACM IPDPS WMAN，2003，(4)：219—227.

[7]HELMY A，CHITRADURGA R.Analysis of short cuts in wireless sensor networks[C].Proceedings of the The IEEE/ACS International Conference on Pervasive Services(ICPS'04)，July 19-23，2004：167-176.

[8]王小平，曹立明，遺傳算法---理論、應用與軟件開發(fā)[M].西安交通大學出版社，2002.

[9]Zhao Chunhua，Yu Zhiqiang，Chen Peng.Optimal deployment of nodes based on genetic algorithm in heterogeneous sensor networks[C].2007 International Conference on Wireless Communications，Networking and Mobile Computing，WiCOM，2007：2743-2746.