基于柵格的傳感網(wǎng)多移動(dòng)Sink數(shù)據(jù)收集方案

楊 瑞，沙 超，卞 遙，朱毅凱，王汝傳

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210003；2.南京大學(xué) 網(wǎng)絡(luò)信息中心，江蘇 南京 210023)

0 引 言

在傳統(tǒng)無(wú)線傳感網(wǎng)(wireless sensor networks，WSNs)中，Sink周圍的節(jié)點(diǎn)不僅需要感知其所覆蓋的區(qū)域，還要負(fù)責(zé)全網(wǎng)的數(shù)據(jù)傳輸，故生命期較短，易形成能量空洞[1]。“能量空洞現(xiàn)象”指的是由于部分節(jié)點(diǎn)失效而導(dǎo)致網(wǎng)絡(luò)原有覆蓋區(qū)域缺失或數(shù)據(jù)無(wú)法送達(dá)Sink的現(xiàn)象[2]。Lian等[3]指出，分布在Sink一跳范圍內(nèi)的節(jié)點(diǎn)更易過(guò)早地耗盡自身能量，而在此情況下，網(wǎng)絡(luò)約有90%的初始能量還未被使用。因此，如何均衡節(jié)點(diǎn)的通信能耗，從而延長(zhǎng)網(wǎng)絡(luò)生命期，成為該領(lǐng)域研究者面對(duì)的首要問(wèn)題[4-5]。

路由優(yōu)化機(jī)制是緩解無(wú)線傳感網(wǎng)能量空洞現(xiàn)象的主要方法[6]，但卻未能從根本上解決靜態(tài)Sink附近的節(jié)點(diǎn)負(fù)載過(guò)重的問(wèn)題。而引入移動(dòng)Sink，不僅可均衡節(jié)點(diǎn)能耗，也縮短了數(shù)據(jù)上傳的距離，降低了全網(wǎng)通信開銷[7]并可有效延長(zhǎng)網(wǎng)絡(luò)生命期[8]。文獻(xiàn)[9]提出了面向能耗均衡的傳感網(wǎng)單移動(dòng)Sink數(shù)據(jù)收集方法，利用網(wǎng)絡(luò)完全覆蓋模型，確定了Sink的各遍歷點(diǎn)坐標(biāo)，并由此構(gòu)建了其定長(zhǎng)移動(dòng)數(shù)據(jù)收集軌跡。Khan等[10]則設(shè)計(jì)了一種基于柵格的數(shù)據(jù)傳播機(jī)制-VGDD(virtual grid based data dissemination)，將網(wǎng)絡(luò)劃分成若干規(guī)模一致的柵格，并在各柵格中根據(jù)節(jié)點(diǎn)到柵格中心的距離選出一個(gè)簇頭。

在數(shù)據(jù)收集過(guò)程中，Sink以固定速度在以矩形網(wǎng)絡(luò)內(nèi)切橢圓為軌跡的線路上移動(dòng)，而全網(wǎng)節(jié)點(diǎn)則通過(guò)其簇頭及若干中繼，將數(shù)據(jù)多跳上傳至Sink。由于Sink的位置不斷變化，故在VGDD中，每個(gè)節(jié)點(diǎn)需實(shí)時(shí)獲取Sink的坐標(biāo)，并由此重建數(shù)據(jù)上傳路徑。文獻(xiàn)[11]提出了一種基于虛擬節(jié)點(diǎn)優(yōu)先級(jí)的移動(dòng)Sink路徑選擇優(yōu)化算法，以滿足時(shí)延約束和最小化網(wǎng)絡(luò)整體能耗為優(yōu)化目標(biāo)展開設(shè)計(jì)；而在早期的工作中[12]，提出了一種基于虛擬區(qū)域的數(shù)據(jù)采集方法-VRDG(virtual region based data gathering)，將網(wǎng)絡(luò)劃分為若干個(gè)由三個(gè)數(shù)據(jù)收集單元組成的虛擬片區(qū)，并在各片區(qū)中根據(jù)節(jié)點(diǎn)剩余能量及其與區(qū)域中心的距離選出遍歷點(diǎn)。

移動(dòng)Sink以恒定速度訪問(wèn)各遍歷點(diǎn)，而片區(qū)內(nèi)的節(jié)點(diǎn)則構(gòu)建了基于“最大前進(jìn)距離”的數(shù)據(jù)上傳路徑，有效提升了數(shù)據(jù)收集效率。文獻(xiàn)[13]提出了一種基于多移動(dòng)Sink的高效數(shù)據(jù)收集協(xié)議-EPBM(efficient data collection protocol based on multiple Sinks)，將網(wǎng)絡(luò)分為4個(gè)面積相等的子域，根據(jù)各子域內(nèi)節(jié)點(diǎn)的覆蓋率及死亡率依次確定子域內(nèi)Sink的移動(dòng)軌跡和運(yùn)動(dòng)狀態(tài)。在數(shù)據(jù)收集過(guò)程中，僅有簇頭向移動(dòng)Sink上傳數(shù)據(jù)，從而延長(zhǎng)了網(wǎng)絡(luò)的生命期。

在上述研究的基礎(chǔ)上，文中設(shè)計(jì)并實(shí)現(xiàn)了一種基于柵格的無(wú)線傳感網(wǎng)數(shù)據(jù)收集方案-GBDG(grid based data gathering)。多個(gè)移動(dòng)Sink在各柵格間分布式地開展數(shù)據(jù)收集，并根據(jù)各鄰居?xùn)鸥癞?dāng)前狀態(tài)(節(jié)點(diǎn)數(shù)據(jù)收集總量、是否有數(shù)據(jù)溢出、柵格內(nèi)節(jié)點(diǎn)剩余能量等)決定下一個(gè)遍歷點(diǎn)。不僅確保了數(shù)據(jù)收集的公平性和節(jié)點(diǎn)能耗的均衡性，同時(shí)也有效降低了數(shù)據(jù)收集時(shí)延。

1 網(wǎng)絡(luò)模型

不失一般性，令網(wǎng)絡(luò)為一個(gè)M×M的矩形區(qū)域，N個(gè)不可移動(dòng)的節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)部署。除移動(dòng)Sink外，所有節(jié)點(diǎn)的初始能量均為E0。同文獻(xiàn)[10]類似，將網(wǎng)絡(luò)劃分為若干面積相等的柵格，如圖1所示。柵格總數(shù)Cnum由N決定，見式1。

Cnum=?N/50」2

(1)

故各柵格的邊長(zhǎng)Cl可表示為：

(2)

圖1 劃分柵格及確定逗留點(diǎn)

由文獻(xiàn)[14]可知，當(dāng)Sink位于網(wǎng)絡(luò)的中心位置時(shí)，網(wǎng)絡(luò)的通信總能耗最小。故令每個(gè)柵格的中心位置為移動(dòng)Sink的逗留點(diǎn)，命名為C。在圖1中，逗留點(diǎn)間的虛線是移動(dòng)Sink可能的移動(dòng)軌跡。在后續(xù)數(shù)據(jù)收集過(guò)程中，各移動(dòng)Sink將以恒定速度沿此虛線在柵格間移動(dòng)。

目前，仍普遍采用經(jīng)典的Heinzelman模型[15]作為無(wú)線傳感網(wǎng)的通信能耗計(jì)算依據(jù)，如式3～5所示。

(3)

Er=Eelec

(4)

(5)

其中，εfs為自由空間模型的功率放大能耗；εamp為功率放大電路的放大系數(shù)；Et和Er分別為發(fā)送和接收1比特?cái)?shù)據(jù)包的能耗；d為節(jié)點(diǎn)間距；d0為參考距離。

于是，在簇樹狀的無(wú)線傳感網(wǎng)中，任一節(jié)點(diǎn)Si的生命期Lnode(Si)可由式6求得。

Lnode(Si)=

(6)

其中，E(Si)為Si的剩余能量；k為節(jié)點(diǎn)單位時(shí)間內(nèi)產(chǎn)生的數(shù)據(jù)量；sub(Si)為Si子孫節(jié)點(diǎn)的數(shù)目。

2 算法描述

2.1 柵格內(nèi)數(shù)據(jù)上傳路徑的構(gòu)建

在GBDG中，柵格內(nèi)的節(jié)點(diǎn)將數(shù)據(jù)上傳至移動(dòng)Sink的方式，是決定其數(shù)據(jù)收集效率的關(guān)鍵。在各柵格內(nèi)，以C點(diǎn)為根，分別建立數(shù)據(jù)收集樹，如圖2所示。首先，將C點(diǎn)一跳通信范圍內(nèi)的所有節(jié)點(diǎn)作為其直接子節(jié)點(diǎn)(由于Sink僅在C點(diǎn)開展數(shù)據(jù)收集，故這些直接子節(jié)點(diǎn)也就是Sub_Sink節(jié)點(diǎn))，即數(shù)據(jù)收集樹的第一層節(jié)點(diǎn)，如圖2中的S1、S2、S3。

圖2 數(shù)據(jù)收集樹的構(gòu)建

柵格中，當(dāng)前位于第k層的節(jié)點(diǎn)，將其鄰居中尚不在樹中的節(jié)點(diǎn)作為樹的第k+1層節(jié)點(diǎn)。第k+1層的節(jié)點(diǎn)，分別將距離自己最近的一個(gè)第k層節(jié)點(diǎn)作為父節(jié)點(diǎn)(圖2中節(jié)點(diǎn)S7選擇了距離其更近的S2作為父節(jié)點(diǎn)，而非S3)，隨后，繼續(xù)找尋第k+2層節(jié)點(diǎn)，直至柵格內(nèi)的所有節(jié)點(diǎn)都加入數(shù)據(jù)收集樹為止。

2.2 相鄰柵格間中繼節(jié)點(diǎn)的選擇

當(dāng)數(shù)據(jù)收集樹構(gòu)建完成后，處于各柵格中的Sink便移動(dòng)至其逗留點(diǎn)C，作為樹的根節(jié)點(diǎn)，開始數(shù)據(jù)收集。GBDG規(guī)定，在網(wǎng)絡(luò)開始運(yùn)行時(shí)，多個(gè)Sink隨機(jī)部署在網(wǎng)絡(luò)中，但不允許同一柵格中同時(shí)存在一個(gè)以上的Sink。當(dāng)Sink完成當(dāng)前柵格的數(shù)據(jù)收集后，將移動(dòng)至其所在柵格的鄰居?xùn)鸥?，繼續(xù)開展數(shù)據(jù)收集。鄰居?xùn)鸥袷侵概c當(dāng)前柵格有共同邊的柵格。然而，對(duì)于一個(gè)柵格，其鄰居?xùn)鸥癫恢挂粋€(gè)，且各柵格的狀態(tài)(如當(dāng)前是否有節(jié)點(diǎn)數(shù)據(jù)溢出、是否有移動(dòng)Sink正在該柵格收集數(shù)據(jù)、柵格內(nèi)的節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)量多少等)也不完全相同。故Sink需根據(jù)各鄰居?xùn)鸥竦臓顟B(tài)來(lái)決定在下一時(shí)刻向哪個(gè)柵格移動(dòng)。為方便將鄰居?xùn)鸥竦臓顟B(tài)信息發(fā)送給移動(dòng)Sink，需要為每個(gè)柵格選一個(gè)簇頭，該簇頭為距離逗留點(diǎn)最近的節(jié)點(diǎn)。然而，由于相鄰柵格間兩個(gè)逗留點(diǎn)的直線距離大于節(jié)點(diǎn)通信半徑，故需要在Sink和其相鄰柵格的簇頭間找尋適量的中繼節(jié)點(diǎn)，發(fā)送柵格的狀態(tài)信息。這里以圖1中的柵格A0和A1為例來(lái)說(shuō)明該過(guò)程。

1．對(duì)于柵格A0和A1的所有節(jié)點(diǎn)，若其通信范圍與連接?xùn)鸥馎0和A1逗留點(diǎn)的虛線相交，則被選為準(zhǔn)中繼節(jié)點(diǎn)。

2．在柵格A0和A1中，離逗留點(diǎn)最近的準(zhǔn)中繼節(jié)點(diǎn)被選為該柵格內(nèi)的第1個(gè)中繼節(jié)點(diǎn)。

3．對(duì)于柵格A0中所選出的第i個(gè)中繼節(jié)點(diǎn)Si，若有準(zhǔn)中繼節(jié)點(diǎn)同時(shí)滿足以下兩個(gè)條件，則其成為第i+1個(gè)中繼節(jié)點(diǎn)。

(1)該準(zhǔn)中繼節(jié)點(diǎn)在Si的通信范圍內(nèi)。

(2)該準(zhǔn)中繼節(jié)點(diǎn)到柵格A1的逗留點(diǎn)的直線距離小于Si到該逗留點(diǎn)的直線距離。

若滿足上述條件的準(zhǔn)中繼節(jié)點(diǎn)不止一個(gè)，則按照式7計(jì)算其各自p值。p值最小者即為第i+1個(gè)中繼節(jié)點(diǎn)。

p=d(Si,Si-1)×vd(Si)

(7)

其中，d(Si,Si-1)指的是Si到Si-1的距離；vd(Si)指的是節(jié)點(diǎn)Si到虛線的垂直距離，如圖3所示。

圖3 中繼節(jié)點(diǎn)的選擇

柵格A0和A1同時(shí)執(zhí)行上述操作，若兩邊的中繼節(jié)點(diǎn)能互相通信時(shí)，中繼節(jié)點(diǎn)選擇完畢。而當(dāng)有中繼節(jié)點(diǎn)死亡時(shí)，也將按此方式重新選擇中繼。

2.3 柵格狀態(tài)的設(shè)定與鄰居?xùn)鸥竦倪x擇

當(dāng)中繼節(jié)點(diǎn)選出后，收集完數(shù)據(jù)的移動(dòng)Sink便開始通過(guò)這些中繼向其鄰居?xùn)鸥竦拇仡^發(fā)送查詢消息。收到查詢消息的簇頭，將其所在柵格的信息反饋給發(fā)出查詢的Sink。這些信息包括：

(1)該柵格內(nèi)所有節(jié)點(diǎn)目前尚未上傳的數(shù)據(jù)總量；

(2)該柵格內(nèi)是否有節(jié)點(diǎn)的緩存已經(jīng)溢出；

(3)該柵格內(nèi)是否有移動(dòng)Sink；

(4)是否有其他移動(dòng)Sink正準(zhǔn)備向該柵格移動(dòng)。

收到反饋的移動(dòng)Sink根據(jù)以上信息確定鄰居?xùn)鸥竦臓顟B(tài)，具體方法為：

(1)當(dāng)柵格中有節(jié)點(diǎn)緩存溢出時(shí)，將此柵格標(biāo)記為黑色；

(2)當(dāng)柵格中有節(jié)點(diǎn)所緩存的數(shù)據(jù)量大于dv時(shí)，將其標(biāo)記為灰色，否則，將其標(biāo)記為白色。dv的計(jì)算見式8。

(8)

其中，U為該柵格內(nèi)所有節(jié)點(diǎn)組成的集合；cache(Si)為節(jié)點(diǎn)Si所能存儲(chǔ)數(shù)據(jù)量的最大值；v為Sink的移動(dòng)速度。

于是，移動(dòng)Sink將根據(jù)當(dāng)前鄰居?xùn)鸥駹顟B(tài)，來(lái)決定下一次移往的柵格。

(1)定義所有鄰居?xùn)鸥窠M成的集合為Une，所有黑色狀態(tài)的鄰居?xùn)鸥窠M成的集合為Bne，所有灰色狀態(tài)的鄰居?xùn)鸥窠M成的集合為Gne，所有白色狀態(tài)的鄰居?xùn)鸥窠M成的集合為Wne。

(2)若鄰居?xùn)鸥裰写嬖谄渌鸖ink或已有其他移動(dòng)Sink正在向其移動(dòng)時(shí)，則該鄰居?xùn)鸥癫蛔鳛槟繕?biāo)柵格的考量。設(shè)這樣的柵格組成的集合為Nne。

(3)令target=Bne∩(Une-Nne)，若size(target)>0，轉(zhuǎn)步驟6。

(4)令target=Gne∩(Une-Nne)，若size(target)>0，轉(zhuǎn)步驟6。

(5)令target=Wne∩(Une-Nne)。

(6)若size(target)=1，則集合target內(nèi)所包含的那個(gè)柵格作為Sink的下一個(gè)移動(dòng)?xùn)鸥?；否則，對(duì)于集合target內(nèi)每一個(gè)柵格Aj，計(jì)算其Pj值，Pj值最大的柵格作為下一個(gè)移動(dòng)?xùn)鸥瘛?/p>

(9)

其中，size(target)表示集合target中元素的個(gè)數(shù)；Ti表示當(dāng)前時(shí)間與節(jié)點(diǎn)i上次傳輸數(shù)據(jù)給Sink的時(shí)間差；ds(i)表示節(jié)點(diǎn)i當(dāng)前緩存的數(shù)據(jù)量。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證GBDG的性能，分別在網(wǎng)絡(luò)生命期、平均通信能耗、數(shù)據(jù)收集延遲、數(shù)據(jù)傳輸成功率等方面與VRDG、VGDD進(jìn)行比較。如無(wú)特殊說(shuō)明，網(wǎng)內(nèi)節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)通信半徑，將分別設(shè)為200個(gè)和20 m，網(wǎng)絡(luò)規(guī)模為200 m×200 m，移動(dòng)Sink的移動(dòng)速度為5 m/s。

圖4是三種算法在數(shù)據(jù)收集延遲方面的性能對(duì)比。這里將數(shù)據(jù)收集延遲定義為移動(dòng)Sink完成一輪數(shù)據(jù)收集的時(shí)間。在VRDG中，Sink的移動(dòng)軌跡是固定的，由所有片區(qū)的簇頭連接而成。移動(dòng)Sink需遍歷完所有簇頭，才能完成一次數(shù)據(jù)收集，故其數(shù)據(jù)收集延遲要高于GBDG。而在VGDD中，Sink的移動(dòng)軌跡是矩形的內(nèi)切橢圓，其長(zhǎng)度同樣是定值，故其數(shù)據(jù)收集延遲僅與網(wǎng)絡(luò)規(guī)模有關(guān)。在該實(shí)驗(yàn)中，網(wǎng)絡(luò)邊長(zhǎng)為200 m，因此，VGDD的移動(dòng)軌跡長(zhǎng)度長(zhǎng)于GBDG，即其數(shù)據(jù)收集延遲高于GBDG。此外，由于GBDG利用了多個(gè)移動(dòng)Sink開展數(shù)據(jù)收集，且每個(gè)柵格在一輪數(shù)據(jù)收集過(guò)程中，最多只會(huì)被一個(gè)Sink訪問(wèn)，從而大大降低了數(shù)據(jù)收集節(jié)點(diǎn)等待上傳的時(shí)間。

圖4 數(shù)據(jù)收集延遲

圖5是數(shù)據(jù)傳輸成功率的實(shí)驗(yàn)結(jié)果。

圖5 數(shù)據(jù)傳輸成功率

與GBDG相比，VGDD在數(shù)據(jù)傳輸成功率方面具備一定優(yōu)勢(shì)。因?yàn)槠淦瑓^(qū)中的簇頭無(wú)需長(zhǎng)時(shí)間緩存數(shù)據(jù)，只要確定了移動(dòng)Sink的位置，柵格便可通過(guò)網(wǎng)絡(luò)內(nèi)的其他簇頭，建立到達(dá)移動(dòng)Sink的多跳數(shù)據(jù)上傳路徑。然而，這樣將增大網(wǎng)絡(luò)的通信開銷。而在VRDG中，片區(qū)數(shù)量較多，且Sink必須按序移動(dòng)至各片區(qū)開展數(shù)據(jù)收集，易造成部分節(jié)點(diǎn)因等待Sink的時(shí)間過(guò)長(zhǎng)而產(chǎn)生緩存溢出。因此，其數(shù)據(jù)傳輸成功率較低。

圖6是三種算法的網(wǎng)絡(luò)生命期對(duì)比。

圖6 網(wǎng)絡(luò)生命期

GBDG由于采用了多個(gè)移動(dòng)Sink開展數(shù)據(jù)收集，且充分考慮了鄰居?xùn)鸥竦臓顟B(tài)，故其能耗均衡性較好，網(wǎng)絡(luò)生命期最長(zhǎng)。此外，與VGDD和VRDG不同，GBDG的網(wǎng)絡(luò)生命期并非隨節(jié)點(diǎn)的通信半徑的增大而降低。這是由于隨著節(jié)點(diǎn)通信半徑的增大，GBDG中與移動(dòng)Sink直接通信的節(jié)點(diǎn)數(shù)量也隨之增加，使得每個(gè)節(jié)點(diǎn)的子孫節(jié)點(diǎn)的數(shù)量減少，各節(jié)點(diǎn)的平均負(fù)載也因此降低，從而延長(zhǎng)了網(wǎng)絡(luò)生命期。

4 結(jié)束語(yǔ)

利用多個(gè)移動(dòng)Sink分布式地在各柵格間開展數(shù)據(jù)收集。重點(diǎn)實(shí)現(xiàn)了基于不同柵格狀態(tài)的多Sink移動(dòng)方案的設(shè)計(jì)。不僅提升了無(wú)線傳感網(wǎng)的數(shù)據(jù)收集效率，也有效降低了延遲，延長(zhǎng)了網(wǎng)絡(luò)生命期。

然而，在實(shí)際應(yīng)用中，移動(dòng)Sink自身的能量和存儲(chǔ)空間并非無(wú)限。如何在該約束下，進(jìn)一步優(yōu)化多Sink的移動(dòng)路徑以及更好地實(shí)現(xiàn)多Sink間的協(xié)同，將是下一步的研究方向。