無(wú)線傳感網(wǎng)絡(luò)中機(jī)會(huì)性的組播路由

聶 燕 柳

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院 河南 新鄭 451100)

0 引 言

傳統(tǒng)的基于數(shù)據(jù)收集的無(wú)線傳感網(wǎng)絡(luò)WSNs[1-2]能夠支持多對(duì)一(Many-to-one)的流量模型。多個(gè)源節(jié)點(diǎn)向單個(gè)目的節(jié)點(diǎn)(信宿)傳輸數(shù)據(jù)，如以信宿為根的數(shù)據(jù)收集樹(shù)。而一些數(shù)據(jù)收集協(xié)議也支持沿著根向葉的數(shù)據(jù)傳輸，即形成一對(duì)多(One-to-Many)流量模型。此外，一些數(shù)據(jù)收集協(xié)議具有一定擴(kuò)展性，對(duì)它們進(jìn)行修剪，它們也能支持多個(gè)源節(jié)點(diǎn)向潛在多目的節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)，即多對(duì)任意(Many-to-any)節(jié)點(diǎn)。

然而，目前缺乏多對(duì)多(Many-to-Many)的數(shù)據(jù)收集協(xié)議，即組播協(xié)議[3]。設(shè)計(jì)有效的組播協(xié)議的挑戰(zhàn)之一：WSNs中無(wú)線電常采用值日周期DC(Duty-Cycled)策略，即周期性或事件觸發(fā)型地關(guān)掉、開(kāi)啟無(wú)線電，進(jìn)而保存節(jié)點(diǎn)能量。但當(dāng)一個(gè)節(jié)點(diǎn)要接收數(shù)據(jù)包時(shí)，發(fā)送節(jié)點(diǎn)的無(wú)線電和接收節(jié)點(diǎn)的無(wú)線電都必須開(kāi)啟。因此，如何給發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)安排一個(gè)短暫的同時(shí)開(kāi)啟無(wú)線電的時(shí)間成為WSNs的關(guān)鍵[4]。發(fā)送節(jié)點(diǎn)等待接收節(jié)點(diǎn)開(kāi)啟無(wú)線電的時(shí)間越長(zhǎng)，發(fā)送節(jié)點(diǎn)所消耗的能量也就越多。若發(fā)送節(jié)點(diǎn)需要等待多個(gè)接收節(jié)點(diǎn)，如組播，則發(fā)送節(jié)點(diǎn)將消耗更多能量，這些因素加劇了設(shè)計(jì)組播協(xié)議的難度。而機(jī)會(huì)模型能夠有效地提高數(shù)據(jù)收集的能效、時(shí)延和可靠性。機(jī)會(huì)模型允許節(jié)點(diǎn)依據(jù)網(wǎng)絡(luò)條件和事件動(dòng)態(tài)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，這就增加了發(fā)送節(jié)點(diǎn)在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的空間。

若采用單一轉(zhuǎn)發(fā)節(jié)點(diǎn)，發(fā)送節(jié)點(diǎn)需等待預(yù)選的轉(zhuǎn)發(fā)節(jié)點(diǎn)喚醒，這必然增加時(shí)延和能耗。而相比于單一轉(zhuǎn)發(fā)節(jié)點(diǎn)，構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集(多個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn))，可以有效地降低轉(zhuǎn)發(fā)時(shí)延。一旦構(gòu)建了轉(zhuǎn)發(fā)節(jié)點(diǎn)集，發(fā)送節(jié)點(diǎn)能夠機(jī)會(huì)性將數(shù)據(jù)傳輸轉(zhuǎn)發(fā)節(jié)點(diǎn)集內(nèi)第一個(gè)喚醒的節(jié)點(diǎn)。一方面，降低了轉(zhuǎn)發(fā)時(shí)延，另一方面，也增加鏈路的強(qiáng)健性，提高數(shù)據(jù)傳輸?shù)姆€(wěn)定性，降低能耗。

為此，本文提出基于機(jī)會(huì)性組播路由OMR(Opportunistic Multicasting routing)。OMR路由考慮多個(gè)目的節(jié)點(diǎn)，先構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集，再?gòu)霓D(zhuǎn)發(fā)節(jié)點(diǎn)集內(nèi)選擇一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，通過(guò)此轉(zhuǎn)發(fā)節(jié)點(diǎn)向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包復(fù)本，直到所有目的節(jié)點(diǎn)均接收到數(shù)據(jù)包。仿真結(jié)果表明，提出的OMR路由能夠有效地提高能效，并降低傳輸時(shí)延。

1 OMR路由

OMR路由是基于DC的異步MAC協(xié)議。每個(gè)節(jié)點(diǎn)周期地廣播beacon包，節(jié)點(diǎn)通過(guò)交互beacon包，獲取鄰居節(jié)點(diǎn)信息。在廣播beacon間隔TF內(nèi)，所有的潛在轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)入休眠狀態(tài)[6]，休眠時(shí)間從[0.5TW,1.5TW]中內(nèi)隨機(jī)選擇，其中TW由網(wǎng)絡(luò)設(shè)定的喚醒間隔，即節(jié)點(diǎn)的期望休眠時(shí)間。

OMR模型主要由轉(zhuǎn)發(fā)節(jié)點(diǎn)集的構(gòu)建FSS(Forwarder set selection)、目的節(jié)點(diǎn)代表的委派DD(Destination Delegation)兩個(gè)階段構(gòu)成。在FSS階段，源節(jié)點(diǎn)決定哪些鄰居節(jié)點(diǎn)可以作為數(shù)據(jù)包的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。當(dāng)構(gòu)建轉(zhuǎn)發(fā)集后，發(fā)送節(jié)點(diǎn)再?gòu)霓D(zhuǎn)發(fā)集中選擇一個(gè)能向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，這個(gè)過(guò)程稱為DD階段。

1.1 FSS階段

所謂組播，就是數(shù)據(jù)包有多個(gè)目的節(jié)點(diǎn)，這樣的數(shù)據(jù)包稱為組播數(shù)據(jù)包。假定數(shù)據(jù)包的目的地址集為D,發(fā)送節(jié)點(diǎn)必須決定哪些鄰居節(jié)點(diǎn)能夠轉(zhuǎn)發(fā)數(shù)據(jù)包(成為轉(zhuǎn)發(fā)節(jié)點(diǎn))。

節(jié)點(diǎn)覆蓋：若一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)能夠向目的節(jié)點(diǎn)d∈D傳遞數(shù)據(jù)包，則說(shuō)明該轉(zhuǎn)發(fā)節(jié)點(diǎn)能夠覆蓋d。對(duì)于任意一個(gè)組播數(shù)據(jù)包，要求組播轉(zhuǎn)發(fā)節(jié)點(diǎn)能夠覆蓋所有目的節(jié)點(diǎn)d∈D。轉(zhuǎn)發(fā)節(jié)點(diǎn)集內(nèi)至少有一個(gè)節(jié)點(diǎn)覆蓋每個(gè)目的節(jié)點(diǎn)。

盡管最初將鄰居節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，但后期須從這些鄰居節(jié)點(diǎn)選擇一些合適的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。為此，本文引用兩個(gè)簡(jiǎn)單的啟發(fā)式算法構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)。這兩個(gè)算法僅依據(jù)路由梯度內(nèi)的信息選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。

接下來(lái)以圖1為例，分析這兩個(gè)算法的具體的實(shí)施過(guò)程。

(a) 以節(jié)點(diǎn)5為目的節(jié)點(diǎn)的梯度 (b) 以節(jié)點(diǎn)6為目的節(jié)點(diǎn)梯度 圖1 構(gòu)建轉(zhuǎn)發(fā)集示例

如圖1所示，假定數(shù)據(jù)包的目的節(jié)點(diǎn)集D={5,6}。圖1(a)、(b)分別顯示以節(jié)點(diǎn)5、6為目的節(jié)點(diǎn)的梯度。接下來(lái)，以構(gòu)建節(jié)點(diǎn)1的轉(zhuǎn)發(fā)節(jié)點(diǎn)集為例，說(shuō)明Union算法和MCS算法構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集的過(guò)程。

表1 以Union算法構(gòu)建轉(zhuǎn)發(fā)集

表2 以MCS算法構(gòu)建轉(zhuǎn)發(fā)集

1.2 DD階段

接下來(lái)，進(jìn)行目的節(jié)點(diǎn)代表的委派工作。所謂目的節(jié)點(diǎn)代表就是將部分目的節(jié)點(diǎn)作為節(jié)點(diǎn)j的目的節(jié)點(diǎn)[7]。假定指定給節(jié)點(diǎn)j的目的節(jié)點(diǎn)集為Dj。對(duì)于任意一個(gè)目的節(jié)點(diǎn)d∈D，如果滿足下式，則將節(jié)點(diǎn)d加入Dj。

(1)

圖2 構(gòu)建DD階段示例

1.3 OMR路由流程

隨后，等待Dj內(nèi)的目的節(jié)點(diǎn)喚醒。一旦Dj內(nèi)有目的節(jié)點(diǎn)喚醒(假定節(jié)點(diǎn)d)，節(jié)點(diǎn)j將就數(shù)據(jù)包傳輸至d，并將d從Dj中刪除。再判斷Dj是否為空，若為空，則結(jié)束。否則，再等待Dj的其余節(jié)點(diǎn)喚醒，重復(fù)上述過(guò)程,直到Dj為空。整個(gè)路由流程如圖3所示。

圖3 OMR算法流程圖

節(jié)點(diǎn)3等待目的節(jié)點(diǎn)喚醒，一旦有喚醒，就將數(shù)據(jù)包傳輸至喚醒它的目的節(jié)點(diǎn)[8]。如圖4(c)所示，目的節(jié)點(diǎn)6先喚醒。隨后，再等待目的節(jié)點(diǎn)5喚醒，一旦喚醒，就將數(shù)據(jù)包傳輸至節(jié)點(diǎn)5，如圖4(d)所示。

(a) 初始狀態(tài)(b) 將復(fù)本傳輸至節(jié)點(diǎn)3

(c) 節(jié)點(diǎn)3將復(fù)本傳輸至節(jié)點(diǎn)6

(d) 節(jié)點(diǎn)3將數(shù)據(jù)包傳輸至節(jié)點(diǎn)5圖4 OMR路由示例

2 性能仿真

2.1 仿真環(huán)境

利用MATLAB軟件建立仿真平臺(tái)。引用文獻(xiàn)[9]的RI-MAC機(jī)會(huì)模型作為仿真模型的鏈路層。仿真參數(shù)如表3所示。

表3 仿真參數(shù)

系統(tǒng)中總共部署K個(gè)源節(jié)點(diǎn)，優(yōu)先在區(qū)域的四個(gè)角部署4個(gè)節(jié)點(diǎn)，并在區(qū)域中心部署一個(gè)節(jié)點(diǎn)。剩余的源節(jié)點(diǎn)隨機(jī)部署于區(qū)域內(nèi)。M個(gè)目的節(jié)點(diǎn)也隨機(jī)部署于仿真區(qū)域內(nèi)。在每個(gè)拓?fù)洵h(huán)境下，每個(gè)源節(jié)點(diǎn)以特定間隔產(chǎn)生100個(gè)數(shù)據(jù)包。以下的實(shí)驗(yàn)數(shù)據(jù)是基于50個(gè)拓?fù)浣Y(jié)構(gòu)下所獲取的實(shí)驗(yàn)數(shù)據(jù)的平均值。

為了更好地分析OMR路由性能，選擇文獻(xiàn)[10]的DownTree-Opp和文獻(xiàn)[11]的FROMS進(jìn)行比較，并分析它們的轉(zhuǎn)發(fā)數(shù)據(jù)包所消耗能量(轉(zhuǎn)發(fā)能耗)、傳輸時(shí)延和數(shù)據(jù)包復(fù)本數(shù)。其中轉(zhuǎn)發(fā)能耗表示TX/RX因?qū)嵤┙M播方案，額外消耗能量的單位為單元(Units)，它表示無(wú)線電開(kāi)啟一毫秒所消耗的能量。而傳輸時(shí)延表示從源節(jié)點(diǎn)將數(shù)據(jù)包傳輸至所有組播的目的節(jié)點(diǎn)所消耗的時(shí)間。數(shù)據(jù)包復(fù)本數(shù)是指數(shù)據(jù)包的分裂次數(shù)，次數(shù)越低，性能越好。

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

2.2.1 目的節(jié)點(diǎn)數(shù)對(duì)算法性能的影響

首先分析目的節(jié)點(diǎn)數(shù)對(duì)路由性能的影響，本次實(shí)驗(yàn)參數(shù)：100個(gè)傳感節(jié)點(diǎn)、5個(gè)源節(jié)點(diǎn)，目的節(jié)點(diǎn)數(shù)從1變化至10，步長(zhǎng)為1。仿真數(shù)據(jù)如圖5-圖7所示。

圖5顯示了三個(gè)協(xié)議的轉(zhuǎn)發(fā)能耗隨目的節(jié)點(diǎn)數(shù)的變化情況。由圖5可知，三個(gè)協(xié)議的轉(zhuǎn)發(fā)能耗隨目的節(jié)點(diǎn)數(shù)增加呈增長(zhǎng)趨勢(shì)。這正是所預(yù)期的，目的節(jié)點(diǎn)數(shù)越多，轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù)次數(shù)也越多，所消耗的轉(zhuǎn)發(fā)能量也越多。相比于DownTree-Opp和FROMS協(xié)議，提出的OMR路由的轉(zhuǎn)發(fā)能耗最低。

圖5 轉(zhuǎn)發(fā)能耗

圖6顯示了三個(gè)協(xié)議的傳輸時(shí)延。由圖6可知，目的節(jié)點(diǎn)數(shù)的增加，傳輸時(shí)延也增加。原因在于：目的節(jié)點(diǎn)數(shù)越多，離源節(jié)點(diǎn)距離遠(yuǎn)的概率也就越大，就增加了傳輸時(shí)延。此外，F(xiàn)ROMS協(xié)議的傳輸時(shí)延性能最差，這主要是因?yàn)镕ROMS是依據(jù)最優(yōu)結(jié)構(gòu)樹(shù)傳輸數(shù)據(jù)包，因此，發(fā)送節(jié)點(diǎn)必須等待特定的轉(zhuǎn)發(fā)節(jié)點(diǎn)喚醒，這增加了傳輸時(shí)延。

圖6 傳輸時(shí)延

圖7顯示了三個(gè)協(xié)議的消息復(fù)本數(shù)。由圖7可知，OMR路由的復(fù)本數(shù)遠(yuǎn)低于DownTree-Opp協(xié)議，但它的復(fù)本數(shù)高于FROMS協(xié)議。這說(shuō)明了OMR算法是通過(guò)高的復(fù)本數(shù)換取低能耗、低時(shí)延。

圖7 消息復(fù)本數(shù)

2.2.2 傳感節(jié)點(diǎn)數(shù)對(duì)算法性能的影響

本次實(shí)驗(yàn)分析傳感節(jié)點(diǎn)數(shù)性能的影響，實(shí)驗(yàn)參數(shù)如下：傳感節(jié)點(diǎn)數(shù)從50至200變化，步長(zhǎng)為50；源節(jié)點(diǎn)數(shù)為5，目的節(jié)點(diǎn)為10。

先分析節(jié)點(diǎn)數(shù)對(duì)轉(zhuǎn)發(fā)能耗的影響。由圖8可知，提出OMR路由的轉(zhuǎn)發(fā)能耗性能優(yōu)于DownTree-Opp和FROMS路由。并且，OMR路由的轉(zhuǎn)發(fā)能耗隨節(jié)點(diǎn)數(shù)的增加而下降，原因在于：節(jié)點(diǎn)數(shù)越多，轉(zhuǎn)發(fā)節(jié)點(diǎn)集內(nèi)節(jié)點(diǎn)數(shù)也越多，可選擇的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率就越大。

圖8 轉(zhuǎn)發(fā)能耗

圖9的傳輸時(shí)延數(shù)據(jù)也再次證實(shí)了OMR路由的性能。由圖9可知，相比于FROMS和DownTree-Opp路由，OMR路由的傳輸時(shí)延得到有效的控制。例如，當(dāng)傳感節(jié)點(diǎn)數(shù)為200時(shí)，OMR算法的傳輸時(shí)延約790 ms，而FROMS路由、DownTree-Opp路由的傳輸時(shí)延分別達(dá)到2 200 ms、1 200 ms。

圖9 傳輸時(shí)延

最后，分析了三個(gè)協(xié)議的消息復(fù)本數(shù)。由圖10可知，OMR路由的消息復(fù)本數(shù)仍介于DownTree-Opp和FROMS路由性能之間。DownTree-Opp路由的消息復(fù)本數(shù)最高，原因在于：數(shù)據(jù)包是依據(jù)DownTree協(xié)議傳輸，這就存在樹(shù)葉重疊，導(dǎo)致了更多的數(shù)據(jù)包復(fù)本數(shù)。

圖10 消息復(fù)本數(shù)

2.2.3 源節(jié)點(diǎn)數(shù)對(duì)算法性能的影響

本次實(shí)驗(yàn)分析源節(jié)點(diǎn)數(shù)對(duì)算法性能的影響。實(shí)驗(yàn)參數(shù)：傳感節(jié)點(diǎn)數(shù)為200，目的節(jié)點(diǎn)數(shù)為30，源節(jié)數(shù)分別為5、7、9和10。

圖11顯示了三個(gè)協(xié)議的平均能耗，由圖11可知，平均能耗源節(jié)點(diǎn)數(shù)增加呈增長(zhǎng)趨勢(shì)。原因在于：源節(jié)點(diǎn)數(shù)越多，所發(fā)送的數(shù)據(jù)包越多，消耗的能量肯定越多。對(duì)比圖8不難發(fā)現(xiàn)，目的節(jié)點(diǎn)數(shù)和源節(jié)點(diǎn)數(shù)的增加，消耗了更多能量。這主要因?yàn)椋耗康墓?jié)點(diǎn)數(shù)越多，數(shù)據(jù)包傳輸?shù)拇螖?shù)也就越多。

圖11 轉(zhuǎn)發(fā)能耗

圖12顯示了OMR、FROMS和DownTree-Opp協(xié)議的消息復(fù)本數(shù)。結(jié)合圖10和圖7的數(shù)據(jù)，不難發(fā)現(xiàn)，目的節(jié)點(diǎn)數(shù)和源節(jié)點(diǎn)數(shù)的增加，快速地增加了消息復(fù)本數(shù)。這符合期望：目的節(jié)點(diǎn)越多數(shù)，源節(jié)點(diǎn)需要傳輸?shù)臄?shù)據(jù)包數(shù)就越多，每條消息的復(fù)本數(shù)就越多。

圖12 消息復(fù)本數(shù)

3 結(jié) 語(yǔ)

針對(duì)基于DC的WSNs，提出機(jī)會(huì)性組播路由OMR，使其具備可擴(kuò)展、高能效和高可靠性。OMR路由給每個(gè)給定的發(fā)送節(jié)點(diǎn)，通過(guò)簡(jiǎn)單的啟發(fā)式算法構(gòu)建轉(zhuǎn)發(fā)節(jié)點(diǎn)集，一旦轉(zhuǎn)發(fā)節(jié)點(diǎn)集內(nèi)的節(jié)點(diǎn)喚醒，就將消息復(fù)本傳輸至此節(jié)點(diǎn)，再由此節(jié)點(diǎn)傳輸至目的節(jié)點(diǎn)。仿真數(shù)據(jù)表明，提出的OMR具有低能耗和低時(shí)延性能。

深度分析OMR路由的開(kāi)銷，并降低網(wǎng)絡(luò)維持成本，將是后期研究工作的方向。