謝英輝,胡 君,唐一韜

(1.長沙民政職業(yè)技術學院軟件學院,長沙 410004;2.湖南科技職業(yè)學院軟件學院,長沙 410004)

隨著對信息收集需求的加強,無線傳感網絡WSNs(Wireless Sensor Networks)[1]被廣泛應用于多個領域[2],如康復醫(yī)療、智慧農業(yè)。WSNs是通過在監(jiān)測區(qū)域內部署微型傳感節(jié)點,并由微型傳感節(jié)點感測數(shù)據,再將數(shù)據傳輸至后臺。然而,這些傳感節(jié)點屬微型節(jié)點,一般是由電池供電。它們的節(jié)點能量有限,且傳輸感測數(shù)據需要多跳轉發(fā),這限制了WSNs的應用[3]。

傳統(tǒng)的WSNs中,傳感節(jié)點通過多跳方式向固定的基站傳輸數(shù)據,這容易使得基站附近的節(jié)點參與過多的數(shù)據轉發(fā),消耗了它們大量的能量。為了延緩節(jié)點能量消耗,并提高數(shù)據收集效率,研究者提出基于移動Sink的數(shù)據收集方案。

依據Sink的移動路徑,基于移動Sink的數(shù)據收集方案可分為固定移動、隨機移動和受控移動。例如,文獻[4]提出移動路徑選擇算法(Moving Path Selection Algorithm,MPSA)。MPSA算法依據虛擬力決策移動方向。而文獻[5]引用啟發(fā)式算法,并依據節(jié)點的任務負荷設置優(yōu)先級,進而減少網絡擁塞和時延。同時,該算法利用SMT設置虛擬訪問點,規(guī)劃Sink節(jié)點訪問路徑。此外,Bhadauria等[6]依據網絡內節(jié)點密度對Sink的移動進行調整,并提出基于節(jié)點密度不同的Sink移動速度控制方案。

盡管移動Sink方案能夠有效地提高數(shù)據收集率,但是該方案仍存在一個問題必須解決:Sink的移動路徑的規(guī)劃。顯然,移動路徑的不同,節(jié)點所收集的數(shù)據可能不同,網絡能量消耗也會不同。因此,如何規(guī)劃Sink的移動,進而最大化數(shù)據收集效率是基于移動Sink數(shù)據收集方案的關鍵技術。

目前,有兩個策略規(guī)劃Sink的移動路徑:①移動Sink遍歷網絡內所有傳感節(jié)點;②移動Sink只遍歷一些預先設定的位置,這些位置稱為駐留點RZP(Rendezvous Point)[7]。相比第一個策略,引用RZP的路徑規(guī)劃策略效率更高,能耗更少。圖1顯示了依據RZP收集數(shù)據的示意圖。移動Sink通過遍歷RZP,形成數(shù)據收集路徑。

圖1 基于移動Sink的數(shù)據收集過程

然而,求解RZP是一個NP問題,其受到多個因素影響,如節(jié)點能量、節(jié)點密度。而遺傳算法GA(Genetic Algorithms)根據適者生存,優(yōu)勝劣汰等自然進化規(guī)則來進行搜索計算和問題求解。對許多用傳統(tǒng)數(shù)學難以解決或明顯失效的復雜問題,特別是優(yōu)化問題,GA提供了一個行之有效的新途徑。

簡之,GA模擬自然界優(yōu)勝劣汰的進化現(xiàn)象,把搜索空間映射為遺傳空間,把可能的解編碼成一個向量——染色體,向量的每個元素稱為基因。通過不斷計算各染色體的適應值,選擇最好的染色體,獲得最優(yōu)解。

為此,提出基于遺傳算法的移動Sink數(shù)據采集算法GMSDC(Genetic algorithm-based Mobile Sink Data Collecting)。GMSDC算法利用遺傳算法尋找最優(yōu)的駐留點,Sink再依這些駐留點移動,進而構成最優(yōu)的數(shù)據傳輸路徑。仿真數(shù)據表明,提出的GMSDC算法有效地縮短了數(shù)據收集時間,并降低了Sink移動路徑。

1 系統(tǒng)模型及問題描述

1.1 系統(tǒng)模型

假定n個傳感節(jié)點隨機分布于M×M的方形區(qū)域,并形成自組織的網絡拓撲。此外,傳感節(jié)點和Sink節(jié)點受以下約束條件限制:①傳感節(jié)點是靜止的。一旦部署后,傳感節(jié)點不再為移動,且每個傳感節(jié)點具有唯一的標識;②所有傳感節(jié)點具有相同的通信半徑r;③Sink節(jié)點能夠移動,且它不受能量約束。

1.2 問題的形式化表述

對給定的節(jié)點集S={s1,s2,…,sn}、RZP點集Ω={z1,z2,…,zm}構建無向圖G=(V,E),其中V=S∪Sink,E為邊集合[8]。令R0表示基站位置。令hi,j表示第ith傳感節(jié)點與第jth個RZP點間的距離,且1≤i≤n,1≤j≤m。類似地,令di,j表示第ith個RZP點與第jth個RZP點間的距離,且1≤i≤m,1≤j≤m。

令τ表示Sink在收集數(shù)據時所移動的路徑長度,其定義如式(1)所示:

τ=∑di,j+d1,R0+dm,R0

(1)

式中:d1,R0、dm,R0分別表示第一個RZP點、最后一個RZP點離基站的位置。

提出的GMSDC算法旨在通過GA搜索最優(yōu)的RZP點,并由這些RZP點構成Sink移動路徑,使Sink覆蓋全網絡,以最短的移動路徑實現(xiàn)采集數(shù)據的最大化。令m*表示最優(yōu)的RZP點數(shù),且m*≤m。

因此,可建立式(2)的目標函數(shù):

Minimize(τ)

(2)

約束條件:

2 GAFR算法

GA在求解工程數(shù)學問題方面得到廣泛應用。GA主要涉及到個體(Individual)、適度生存、適應性(Fintess)、群體(Population)、復制(Reproduction)、交配(Crossover)和變異(Mutation)用語。表1這些用語在工程數(shù)學領域的解釋。

表1 GA算法中關鍵用語的解釋

圖2描述了GA執(zhí)行流程。選設定初始群體,并確定種群,再計算各染色體的適應度。隨后,通過存優(yōu)去劣法則產生新的種群[9],并檢測是否滿足預定指標。若滿足,則獲取解,否則繼續(xù)迭代。

圖2 GA的執(zhí)行流程

2.1 染色體編碼

GMSDC算法旨在構建最優(yōu)的RZP,即尋找最優(yōu)的m*。為此,將RZP的IDs編碼成染色體,而染色體的長度等RZP的數(shù)目。當Sink移動至RZP就收集附近傳感節(jié)點的數(shù)據。

RZP的ID就是染色體的基因位置。圖3顯示了兩條染色體。第一條染色體具有10個基因位置,第二條具有12個基因位置。可通過交叉操作改變染色體長度。

圖3 染色體編碼

2.2 種群

對于不同長度的染色體,均采用固定的初始群體尺寸。若采用初始群體數(shù)為N,則只要滿足群體數(shù)為N的染色體才是有效的[10]。群體數(shù)反應了可行解數(shù)。圖2顯示了長度為10、12的兩條染色體,但它們的群體數(shù)均為5(N=5)。

2.3 適度函數(shù)

GA利用適度函數(shù)評估染色體的性能,分析它們適應環(huán)境的能力,使更優(yōu)質的基因得到進化。Sink移動路徑與RZP數(shù)密切相關,也與路徑長度相關。

為此,構建如式(4)所示的適度函數(shù):

F=αL+βτ

(4)

式中:L表示迭代過程中駐留點數(shù),且L≤m。而α、β為權重因子,用于平衡L和τ對適度值F的影響,且α+β=1。

L和τ均為系統(tǒng)因子,是在推導駐留點數(shù)m*過程中的系統(tǒng)變量。如圖4所示,最初先部署RZP,通過GA算法迭代L值,然后判斷是否滿足條件。若滿足,就輸出最優(yōu)m*值,否則就繼續(xù)迭代。本文通過迭代次數(shù)設置終止條件。

圖4 優(yōu)化RZP的過程

2.4 選擇階段

選擇部分染色體進行交叉、變異,進而產生新的種子是GA算法的關鍵。而所選種子的優(yōu)劣直接與染色體的適度值相關。換而言之,可通過染色體的適度值選擇種子。

目前,有多類選擇算法,如輪盤賭選擇、秩值選擇法。本文選用輪盤賭選擇法,其基本思想是:個體被選中的概率與其適應度大小成正比。輪盤賭選擇的執(zhí)行步驟如下所示:

Step 1:計算群體中每個個體的適應度f(xi)i=1,2,…,M

Step 4:從[0,1]區(qū)間內產生一個均勻頒的隨機數(shù)b

Step 5:若b

Step 6:重復執(zhí)行步驟(4)、步驟(5),共M次

2.5 交叉

利用2.4選擇部分染色體,再對這些染色體進行交叉操作?，F(xiàn)存在單點、多點交叉。本文選擇單點交叉[11],如圖5所示。最初,兩條染色體的長度分別為8、12。通過交叉操作,產生長度為10的新的兩條染色體。

圖5 染色體交叉示意圖

2.6 變異

GA使用交叉操作已經從全局的角度出發(fā)找到了一些較好的個體編碼結構,可能已經接近問題最優(yōu)解,但是用交叉操作無法對搜索空間的細節(jié)進行局部搜索,因此通過變異操作[11-12]調整個體編碼串的部分基因值,提高遺傳算法的局部搜索能力。

令變異概率為0.5。每條染色體進行均進行變異,進而提高染色體質量。如圖6所示,染色體2的第5個基因位置發(fā)生變異,由原來的77變成64。

圖6 變異后的操作

3 性能分析

3.1 仿真環(huán)境

通過Python3.5軟件構建仿真平臺,分析GMSDC算法的性能?？紤]在M×M的方形區(qū)域部署50～300個傳感節(jié)點。Sink的移動速度為?=5 m/s,并在駐留點處停留1 s。具體的仿真參數(shù)如表2所示。此外,選擇能量高效的移動Sink數(shù)據收集策略(EDAMS)[8]作為參照,并分析Sink所移動的路徑以及收集數(shù)據所需要的時間。

表2 仿真參數(shù)

3.2 數(shù)據分析

為了更好地節(jié)點密度對算法性能的影響,考慮兩場景。場景一:M=10 m;場景二:M=15 m。

3.2.1 場景一

圖7顯示了Sink移動的路徑長度隨節(jié)點數(shù)的變化情況。從圖7可知,路徑長度隨節(jié)點數(shù)的增加而上升。這主要因為:節(jié)點數(shù)越多,Sink需要收集的數(shù)據越多,就增加Sink的移動路徑。此外,相比于EDAMS算法,GMSDC算法縮短了Sink移動路徑。這主要因為:GMSDC算法通過遺傳算法尋找最優(yōu)的RZP,以最短的路徑完成了數(shù)據的收集。

圖7 路徑長度(場景一)

圖8顯示了Sink收集數(shù)據所耗的時間。時間越短,數(shù)據收集效率越高。從圖8可知,節(jié)點數(shù)的增加拉長了Sink收集數(shù)據時間。原因在于:節(jié)點數(shù)越多,節(jié)點移動路徑越長,必然增加了節(jié)點收集數(shù)據的時間。相比于EDAMS,GMSDC算法的數(shù)據收集效率更高。例如,在節(jié)點數(shù)為250時,EDAMS算法的數(shù)據收集時間達到6 000 s,而GMSDC算法的數(shù)據收集時間只有2 200 s。

圖8 數(shù)據收集時間(場景一)

圖9 路徑長度(場景二)

3.2.2 場景二

本次實驗考慮更大仿真區(qū)域,仿真區(qū)域面積為200 m2。圖9、圖10分別顯示了在仿真區(qū)域200 m2下的Sink移動路徑和數(shù)據收集時間。

從圖9可知,Sink移動路徑仍隨節(jié)點數(shù)的增加而上升。相比圖7,仿真區(qū)域面積的增加,加大了路徑長度。原因在于:區(qū)域面積越大,節(jié)點移動路徑必然增加。例如,在節(jié)點數(shù)為300時,當區(qū)域面積從100 m2增至200 m2時,EDAMS和GMSDC算法的路徑長度分別從1 350、450增加至2 500、900。

圖10顯示了數(shù)據收集時間隨節(jié)點數(shù)的變化情況。從10可知,節(jié)點數(shù)的增加提升了數(shù)據收集時間。相比于圖8,仿真區(qū)域200 m2下的兩個算法的數(shù)據收集時間更長。例如,在節(jié)點數(shù)為250時,當仿真區(qū)域為200 m2降至100 m2時,GMSDC算法的數(shù)據收集時間從5 800 s降至約13 000 s。

圖10 數(shù)據收集時間(場景二)

3.2.3 Sink的移動特性分析

本次實驗分析移動速度以及在RZP的停留時間對移動路徑長度以及數(shù)據收集時間的影響。實驗參數(shù):仿真區(qū)域為100 m2,節(jié)點數(shù)300。

從圖11可知,Sink移動速度的增加,降低了路徑長度,這符合預期。移動速度的加快,加速了GA算法收斂的速度。此外,觀察圖11不難發(fā)現(xiàn),在RZP停留時間對路徑長度影響并不大。在0.5 s～3 s的停留時間內,路徑長度波動范圍小。

圖11 GMSDC算法的路徑長度隨Sink移動 特性變化情況

4 總結

快速有效地收集數(shù)據是多數(shù)基于WSNs應用的關鍵。而移動Sink是快速收集數(shù)據的有效措施?？紤]到Sink的移動路徑受多方因素影響,GMSDC算法引用GA算法選擇RZP點,Sink就依著這些RZP點所構成的路徑進行移動。仿真結果表明,提出的GMSDC算法減少了數(shù)據收集時間。