基于遺傳算法的移動Sink數(shù)據(jù)采集信宿路算法*

謝英輝,胡 君,唐一韜

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

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

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

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

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

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

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

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

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

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

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

1.1 系統(tǒng)模型

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

1.2 問題的形式化表述

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

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

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

(1)

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

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

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

Minimize(τ)

(2)

約束條件:

2 GAFR算法

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

表1 GA算法中關(guān)鍵用語的解釋

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

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

2.1 染色體編碼

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

RZP的ID就是染色體的基因位置。圖3顯示了兩條染色體。第一條染色體具有10個基因位置,第二條具有12個基因位置?？赏ㄟ^交叉操作改變?nèi)旧w長度。

圖3 染色體編碼

2.2 種群

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

2.3 適度函數(shù)

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

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

F=αL+βτ

(4)

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

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

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

2.4 選擇階段

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

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

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

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

Step 5:若b

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

2.5 交叉

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

圖5 染色體交叉示意圖

2.6 變異

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

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

圖6 變異后的操作

3 性能分析

3.1 仿真環(huán)境

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

表2 仿真參數(shù)

3.2 數(shù)據(jù)分析

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

3.2.1 場景一

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

圖7 路徑長度(場景一)

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

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

圖9 路徑長度(場景二)

3.2.2 場景二

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

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

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

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

3.2.3 Sink的移動特性分析

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

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

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

4 總結(jié)

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