能耗與時延權(quán)衡的分布式信息擴(kuò)散方法*

許蒙蒙，陳青，朱海，王娟娟，梁歆培

（1.河南工程學(xué)院計(jì)算機(jī)學(xué)院，河南 鄭州 451191；2.湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，湖北 武漢 430062；3.周口師范學(xué)院網(wǎng)絡(luò)工程學(xué)院，河南 周口 466001）

0 引言

無線傳感器網(wǎng)絡(luò)被廣泛地應(yīng)用于工農(nóng)業(yè)生產(chǎn)、環(huán)境監(jiān)測、城市管理等領(lǐng)域。在這些領(lǐng)域中，基于突發(fā)事件的應(yīng)急信息擴(kuò)散是一個常見的通信模式。例如，當(dāng)出現(xiàn)突發(fā)事故時，道路上行駛的車輛可以迅速產(chǎn)生一條應(yīng)急信息，并擴(kuò)散至一定范圍內(nèi)的其他車輛。在信息擴(kuò)散過程中，能量消耗和傳輸時延是協(xié)議設(shè)計(jì)的兩個重要考慮因素。因此，有必要在傳感器網(wǎng)絡(luò)中研究低能耗、低時延的信息擴(kuò)散方法。

傳感器節(jié)點(diǎn)大多是一個便攜式終端設(shè)備，采用電池供電。低能耗的數(shù)據(jù)信息傳輸可以有效延長無線傳感器網(wǎng)絡(luò)的使用壽命。目前已有許多文獻(xiàn)研究并提出高能效的網(wǎng)絡(luò)協(xié)議，包括收據(jù)收集[1]、物聯(lián)網(wǎng)架構(gòu)[2]、拓?fù)淇刂芠3]、自動化系統(tǒng)[4]等。鑒于數(shù)據(jù)信息傳輸消耗傳感器網(wǎng)絡(luò)的大部分能量，因此在各類網(wǎng)絡(luò)應(yīng)用中尋找最優(yōu)的傳輸路徑成為網(wǎng)絡(luò)協(xié)議設(shè)計(jì)的一個主要研究方向。LUO等[5]在一維線型網(wǎng)絡(luò)中提出了低能耗的機(jī)會路由算法。DING等[6]在軟件定義的傳感器網(wǎng)絡(luò)中設(shè)計(jì)了高能效的中繼節(jié)點(diǎn)選擇算法。樊凌雁等[7]通過優(yōu)化飛行軌跡、傳輸功率等參數(shù)實(shí)現(xiàn)了低能耗的無人機(jī)數(shù)據(jù)傳輸。然而上述研究工作均沒有考慮信息傳輸?shù)臅r效性。

事實(shí)上，信息傳輸?shù)母吣苄酝且愿邆鬏敃r延為代價(jià)的[8-9]?？紤]到在一些網(wǎng)絡(luò)應(yīng)用中數(shù)據(jù)信息擴(kuò)散要求及時性，低時延的數(shù)據(jù)信息傳輸在傳感器網(wǎng)絡(luò)中同樣受到廣泛關(guān)注[10-12]。CHAQFEH等[10]為降低信息傳輸過程中的通信開銷提出了多方向數(shù)據(jù)擴(kuò)散協(xié)議。BHATIA等[11]設(shè)計(jì)了自適應(yīng)的廣播計(jì)時方案，能夠有效減少副本信息傳輸。能量消耗與傳輸時延的權(quán)衡設(shè)計(jì)見文獻(xiàn)[12-15]中的研究工作。然而，上述文獻(xiàn)研究大都是某一類網(wǎng)絡(luò)應(yīng)用中得到的，其成果難以覆蓋多樣化的網(wǎng)絡(luò)應(yīng)用。此外，傳感器網(wǎng)絡(luò)中數(shù)據(jù)信息傳輸也涉及提高吞吐量[16-17]、提升可靠性[18-19]以及隱私保護(hù)[20]等因素。

面向一維線型傳感器網(wǎng)絡(luò)，提出能量消耗與傳輸時延權(quán)衡的分布式信息擴(kuò)散算法。首先，由理論分析推導(dǎo)出信息擴(kuò)散過程中的最優(yōu)傳輸次數(shù)與傳輸距離。然后，根據(jù)理論分析結(jié)果設(shè)計(jì)分布式的信息擴(kuò)散算法以產(chǎn)生最優(yōu)的中繼節(jié)點(diǎn)序列。最后，通過仿真實(shí)驗(yàn)驗(yàn)證所提算法能夠?qū)崿F(xiàn)能量消耗與傳輸時延的折中，且在能耗指標(biāo)上優(yōu)于一些常用算法。

1 系統(tǒng)模型

考慮一維線型無線傳感器網(wǎng)絡(luò)，如圖1所示。若一個傳感器節(jié)點(diǎn)感知到突發(fā)事件，則該傳感器節(jié)點(diǎn)成為源節(jié)點(diǎn)并產(chǎn)生一條應(yīng)急信息。假設(shè)源節(jié)點(diǎn)需要將應(yīng)急信息擴(kuò)散至長度為L的線型區(qū)域內(nèi)其它傳感器節(jié)點(diǎn)。網(wǎng)絡(luò)區(qū)域L內(nèi)均勻地分布著n個傳感器節(jié)點(diǎn)，從左至右分別記為{1,2,…,n}，其中最左端節(jié)點(diǎn)1表示產(chǎn)生應(yīng)急信息的源節(jié)點(diǎn)。記每個傳感器節(jié)點(diǎn)i∈{1,2,…,n}的位置為xi。由于源節(jié)點(diǎn)向兩側(cè)進(jìn)行信息擴(kuò)散的方法相同，因此本文僅考慮右側(cè)信息擴(kuò)散。假設(shè)每個傳感器節(jié)點(diǎn)采用單向天線且最大傳輸范圍記為R。若兩個傳感器節(jié)點(diǎn)i和k之間的距離d(i,k)=|xi-xk|不超過最大傳輸范圍R，則它們可以直接通信，進(jìn)行數(shù)據(jù)傳輸，即無線鏈路lik存在。

圖1 一維線型網(wǎng)絡(luò)示例

數(shù)據(jù)信息在兩節(jié)點(diǎn)之間傳輸?shù)倪^程中會產(chǎn)生能量消耗，包括傳輸能耗Etx和接收能耗Erx。兩節(jié)點(diǎn)之間傳輸一個比特應(yīng)急信息的能量消耗可以表示為：

其中Etx(d)=etx+βdτ，etx表示發(fā)送節(jié)點(diǎn)電路能耗，b表示傳輸單位距離的天線輸出能耗，d表示信息傳輸?shù)木嚯x，t表示路徑損耗因子，滿足2≤t≤4。

源節(jié)點(diǎn)在向網(wǎng)絡(luò)區(qū)域中其它節(jié)點(diǎn)進(jìn)行信息擴(kuò)散的過程中，需要選擇一系列的中繼節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。考慮到信息傳輸?shù)膹V播特性，源節(jié)點(diǎn)將信息傳輸至第一個中繼節(jié)點(diǎn)時，源、中繼節(jié)點(diǎn)之間的其它節(jié)點(diǎn)也會接收到該信息。由文獻(xiàn)[8]，信息擴(kuò)散至網(wǎng)絡(luò)區(qū)域L內(nèi)的所有節(jié)點(diǎn)所需要的時間正比例與傳輸次數(shù)。因此，本文采用傳輸次數(shù)表示應(yīng)急信息擴(kuò)散至網(wǎng)絡(luò)區(qū)域內(nèi)所有節(jié)點(diǎn)的時延。

能耗與時延權(quán)衡的信息擴(kuò)散問題定義如下：給定時延約束，即傳輸次數(shù)約束D，如何通過分布式方法選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)序列，使得應(yīng)急信息擴(kuò)散至網(wǎng)絡(luò)區(qū)域L內(nèi)的所有節(jié)點(diǎn)消耗的能量最小。

2 最優(yōu)的傳輸次數(shù)與傳輸距離

本節(jié)分析一個比特應(yīng)急信息擴(kuò)散至整個網(wǎng)絡(luò)區(qū)域L所需要的能量消耗Etot?；诖耍ㄟ^理論分析計(jì)算得出時延約束下高能效信息擴(kuò)散的最優(yōu)傳輸次數(shù)hop和傳輸距離dop。

假設(shè)源節(jié)點(diǎn)r0=1將應(yīng)急信息擴(kuò)散至整個網(wǎng)絡(luò)區(qū)域L需要h次傳輸，即需要h次中繼傳輸（包含源節(jié)點(diǎn)傳輸）。假設(shè)中繼節(jié)點(diǎn)序列記為 {r0,r1,…,rh-1} ?{1,2,…,n}。于是，源節(jié)點(diǎn)將一個比特?cái)?shù)據(jù)信息擴(kuò)散至整個網(wǎng)絡(luò)區(qū)域L的總能耗Etot可表示為：

其中d(rh-1,rh)表示最后一個中繼節(jié)點(diǎn)rh-1與網(wǎng)絡(luò)區(qū)域右端邊界的距離。

（1）定理1：在一維線型傳感器網(wǎng)絡(luò)中，源節(jié)點(diǎn)1需要在傳輸次數(shù)約束D內(nèi)將應(yīng)急信息以高能效的方式擴(kuò)散至網(wǎng)絡(luò)區(qū)域L內(nèi)其它節(jié)點(diǎn)。根據(jù)總能耗式(2)，最優(yōu)的傳輸次數(shù)為：

最優(yōu)的單跳傳輸距離為：

證明：為實(shí)現(xiàn)信息擴(kuò)散的總能耗Etot最小化，采用均值不等式可得：

為求出最優(yōu)的傳輸次數(shù)hop，假設(shè)傳輸次數(shù)h是連續(xù)的。將最小總能耗對傳輸次數(shù)h求導(dǎo)可得：

進(jìn)行二階求導(dǎo)得：

由二階導(dǎo)數(shù)的意義可得使能耗最小的最優(yōu)傳輸次數(shù)為h*。

考慮傳輸次數(shù)約束D。若h*≤D，則最優(yōu)傳輸次數(shù)即為hop=h*；若h*＞D，則最優(yōu)的傳輸次數(shù)即為D。事實(shí)上，由式(6)、(7)、(8)可知，在區(qū)間（0,h*）為傳輸次數(shù)h的單調(diào)遞減函數(shù)。綜上，最優(yōu)的傳輸次數(shù)為hop=min{h*,D}，即式(3)。進(jìn)而最優(yōu)的單跳傳輸距離為dop=L/hop，即式(4)。

至此，定理1證明結(jié)束。定理1所得出的結(jié)論適用于理想的線型網(wǎng)絡(luò)模型。一方面，最優(yōu)的傳輸次數(shù)hop應(yīng)該為自然數(shù)，而非實(shí)數(shù)。另一方面，在實(shí)際的傳感器網(wǎng)絡(luò)中，中繼節(jié)點(diǎn)若以最優(yōu)傳輸距離進(jìn)行信息擴(kuò)散，并不能有效地降低能耗。這是因?yàn)檫x取的下一跳中繼節(jié)點(diǎn)不可能恰好處于當(dāng)前中繼節(jié)點(diǎn)的dop位置處。因此，下一節(jié)將定義候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集以及優(yōu)先級函數(shù)，進(jìn)而提出中繼節(jié)點(diǎn)序列選擇的分布式算法。

3 分布式中繼節(jié)點(diǎn)選擇

在實(shí)際網(wǎng)絡(luò)中選取最優(yōu)的中繼節(jié)點(diǎn)序列，首先定義當(dāng)前中繼節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集以及選擇下一跳中繼節(jié)點(diǎn)的優(yōu)先級函數(shù)。若當(dāng)前中繼節(jié)點(diǎn)為ri(0 ≤i≤hop-1)，定義中繼節(jié)點(diǎn)ri候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集為其最大傳輸范圍內(nèi)（右側(cè)）的所有鄰節(jié)點(diǎn)，從左向右分別記為F(ri)={h1,…,hk}。顯然，有d(ri,hk)≤R。距離中繼節(jié)點(diǎn)ri的dop位置處稱為選擇下一跳中繼節(jié)點(diǎn)的最優(yōu)位置，即xri+dop。根據(jù)候選轉(zhuǎn)發(fā)節(jié)點(diǎn)與最優(yōu)位置的距離定義下一跳中繼節(jié)點(diǎn)選擇的優(yōu)先級函數(shù)：

一般來講，轉(zhuǎn)發(fā)節(jié)點(diǎn)與最優(yōu)位置越近，選擇其作為下一跳中繼節(jié)點(diǎn)的優(yōu)先級越高。于是，選擇優(yōu)先級最高的轉(zhuǎn)發(fā)節(jié)點(diǎn)作為下一跳中繼節(jié)點(diǎn)。需要說明的是優(yōu)先級函數(shù)可以進(jìn)一步考慮節(jié)點(diǎn)剩余能量、轉(zhuǎn)發(fā)意愿性等其它實(shí)際因素。

接下來提出一維線型傳感器網(wǎng)絡(luò)中能量與時延權(quán)衡的分布式信息擴(kuò)散算法（DIDA,Distributed Information Diffusion Algorithm with Energy-delay Tradeoff）。DIDA算法步驟如下：

（1）建立一維線型傳感器網(wǎng)絡(luò)。初始值ri=r0=1，即源節(jié)點(diǎn)作為第一個中繼節(jié)點(diǎn)。源節(jié)點(diǎn)根據(jù)式(3)計(jì)算最優(yōu)的傳輸次數(shù)hop，按四舍五入取整。再由式(4)計(jì)算最優(yōu)的單跳傳輸距離dop=L/round(hop)，其中round(·) 表示四舍五入取整運(yùn)算。

（2）通過HELLO信息交互，中繼節(jié)點(diǎn)ri獲取鄰節(jié)點(diǎn)的位置信息，并確定候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集F(ri)。

（3）forhj∈F(ri) do

根據(jù)式(9)計(jì)算P(hj)；

end for

（4）中繼節(jié)點(diǎn)ri選擇具有最高優(yōu)先級的轉(zhuǎn)發(fā)節(jié)點(diǎn)作為下一跳中繼節(jié)點(diǎn)ri+1并將選擇結(jié)果廣播給其它轉(zhuǎn)發(fā)節(jié)點(diǎn)。

（5）重復(fù)步驟（2）-（4），直到選擇出最后一個中繼節(jié)點(diǎn)rround(hop)-1。

在DIDA算法中，源節(jié)點(diǎn)根據(jù)應(yīng)急信息需要擴(kuò)散的網(wǎng)絡(luò)區(qū)域L、傳輸次數(shù)約束D以及能耗相關(guān)參數(shù)計(jì)算出最優(yōu)的傳輸次數(shù)與傳輸距離。然后，源節(jié)點(diǎn)將這兩個數(shù)值與應(yīng)急信息一起發(fā)送至第二個中繼節(jié)點(diǎn)。第二個中繼節(jié)點(diǎn)根據(jù)最優(yōu)的傳輸次數(shù)與傳輸距離選擇第三個中繼節(jié)點(diǎn)，以此類推。當(dāng)選擇出第round(hop)-1個中繼節(jié)點(diǎn)后，算法終止。DIDA算法的核心思想來源于第2節(jié)的理論分析，同時考慮網(wǎng)絡(luò)節(jié)點(diǎn)分布的實(shí)際情況，即下一跳中繼節(jié)點(diǎn)不可能恰好處于當(dāng)前中繼節(jié)點(diǎn)的最優(yōu)傳輸位置處。因此，基于DIDA算法生成中繼節(jié)點(diǎn)并進(jìn)行信息擴(kuò)散，產(chǎn)生的能量消耗值會略高于式(5)所計(jì)算的總能耗最小值。

4 仿真結(jié)果

在仿真實(shí)驗(yàn)中，20～60個傳感器節(jié)點(diǎn)隨機(jī)均勻分布在0～300 m的線型區(qū)域內(nèi)。每個傳感器節(jié)點(diǎn)的最大傳輸范圍為R=50 m。假設(shè)產(chǎn)生應(yīng)急信息的源節(jié)點(diǎn)位于原點(diǎn)處，即x1=0。傳感器節(jié)點(diǎn)的能量消耗參數(shù)分別為Erx=etx=50×10-9J/bit，β=100×10-12J/bit/m2，路徑損耗因子τ=2。

首先，考察所提DIDA算法在信息擴(kuò)散過程中能量消耗隨傳輸次數(shù)約束的變化關(guān)系。將傳輸次數(shù)約束從10變化至15，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目設(shè)置為40個。圖2所示為傳輸次數(shù)約束與能量消耗的權(quán)衡曲線。從圖2中可以看出，當(dāng)傳輸次數(shù)約束較為嚴(yán)厲時，信息擴(kuò)散的能量消耗會顯著增加，即低時延的信息擴(kuò)散是以能量消耗增加為代價(jià)的。隨著傳輸次數(shù)約束的放松，信息擴(kuò)散的能量消耗會不斷降低，并趨近于穩(wěn)定值。這是因?yàn)閭鬏敶螖?shù)約束已經(jīng)超過了最優(yōu)的傳輸次數(shù)，信息擴(kuò)散的能量消耗難以繼續(xù)降低。

圖2 能耗與時延權(quán)衡的關(guān)系

其次，以能量消耗與傳輸次數(shù)為性能指標(biāo)，將DIDA算法與兩類常用的信息擴(kuò)散算法進(jìn)行對比：基于距離的貪婪算法（GreedDist,Greedy Distance-based Algorithm）以及地理隨機(jī)轉(zhuǎn)發(fā)算法（GeRaF,Geographic Random Forwarding）。在GreedDist算法中，中繼節(jié)點(diǎn)選擇其轉(zhuǎn)發(fā)節(jié)點(diǎn)集合中最遠(yuǎn)的傳感器節(jié)點(diǎn)作為下一跳中繼節(jié)點(diǎn)；而GeRaF算法則采用隨機(jī)的方式產(chǎn)生下一跳中繼節(jié)點(diǎn)。將節(jié)點(diǎn)數(shù)目從20變化至60，DIDA算法分別取傳輸次數(shù)約束為10與14。信息擴(kuò)散的能量消耗以及傳輸次數(shù)與節(jié)點(diǎn)數(shù)目的關(guān)系分別如圖3和圖4所示：

圖3 能耗與節(jié)點(diǎn)數(shù)目的關(guān)系

圖4 傳輸次數(shù)與節(jié)點(diǎn)數(shù)目的關(guān)系

從圖3可以看出，本文提出的DIDA算法能夠產(chǎn)生最低能耗的中繼節(jié)點(diǎn)選擇方案，特別是在傳輸次數(shù)約束寬松時（即D=14）。此外，能量消耗隨著節(jié)點(diǎn)數(shù)目的增加而增加，這是因?yàn)樾畔U(kuò)散過程中節(jié)點(diǎn)數(shù)目越多，產(chǎn)生的接收能耗就越多。從圖4可以看出，DIDA算法與GreedDist算法的傳輸次數(shù)比較穩(wěn)定。DIDA算法的傳輸次數(shù)由最優(yōu)的傳輸次數(shù)和傳輸次數(shù)約束共同確定，而GreedDist算法的傳輸次數(shù)則由最大傳輸范圍決定。在給出具體的仿真參數(shù)情況下，信息擴(kuò)散最優(yōu)的傳輸次數(shù)為13。因此，傳輸次數(shù)約束為14時，DIDA算法采用最優(yōu)的傳輸次數(shù)；當(dāng)傳輸次數(shù)約束為10時，DIDA算法選擇約束值作為傳輸次數(shù)。顯然，仿真實(shí)驗(yàn)與理論分析結(jié)果一致。

5 結(jié)束語

在傳感器網(wǎng)絡(luò)中，能量消耗和傳輸時延是應(yīng)急信息擴(kuò)散的兩個主要考慮因素。為此，在一維線型傳感器網(wǎng)絡(luò)中提出一種能量消耗與時延權(quán)衡的信息擴(kuò)散方法。首先，通過分析應(yīng)急信息擴(kuò)散至網(wǎng)絡(luò)區(qū)域所有節(jié)點(diǎn)的能量消耗，在傳輸次數(shù)約束（即時延約束）下，理論推導(dǎo)了最優(yōu)的傳輸次數(shù)與傳輸距離。然后，根據(jù)實(shí)際網(wǎng)絡(luò)提出能量消耗與時延權(quán)衡的分布式算法。仿真結(jié)果表明所提算法能夠?qū)崿F(xiàn)能耗與時延的權(quán)衡，且在能耗指標(biāo)上優(yōu)于一些傳統(tǒng)算法。