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

謝英輝,胡 君,唐一韜

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

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

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

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

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

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

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

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

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

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

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

1.1 系統(tǒng)模型

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

1.2 問(wèn)題的形式化表述

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

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

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

(1)

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

提出的GMSDC算法旨在通過(guò)GA搜索最優(yōu)的RZP點(diǎn),并由這些RZP點(diǎn)構(gòu)成Sink移動(dòng)路徑,使Sink覆蓋全網(wǎng)絡(luò),以最短的移動(dòng)路徑實(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é)問(wèn)題方面得到廣泛應(yīng)用。GA主要涉及到個(gè)體(Individual)、適度生存、適應(yīng)性(Fintess)、群體(Population)、復(fù)制(Reproduction)、交配(Crossover)和變異(Mutation)用語(yǔ)。表1這些用語(yǔ)在工程數(shù)學(xué)領(lǐng)域的解釋。

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

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

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

2.1 染色體編碼

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

RZP的ID就是染色體的基因位置。圖3顯示了兩條染色體。第一條染色體具有10個(gè)基因位置,第二條具有12個(gè)基因位置。可通過(guò)交叉操作改變?nèi)旧w長(zhǎng)度。

圖3 染色體編碼

2.2 種群

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

2.3 適度函數(shù)

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

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

F=αL+βτ

(4)

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

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

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

2.4 選擇階段

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

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

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

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

Step 5:若b

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

2.5 交叉

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

圖5 染色體交叉示意圖

2.6 變異

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

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

圖6 變異后的操作

3 性能分析

3.1 仿真環(huán)境

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

表2 仿真參數(shù)

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

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

3.2.1 場(chǎng)景一

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

圖7 路徑長(zhǎng)度(場(chǎng)景一)

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

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

圖9 路徑長(zhǎng)度(場(chǎng)景二)

3.2.2 場(chǎng)景二

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

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

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

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

3.2.3 Sink的移動(dòng)特性分析

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

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

圖11 GMSDC算法的路徑長(zhǎng)度隨Sink移動(dòng) 特性變化情況

4 總結(jié)

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