聶 燕 柳

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

0 引 言

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

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

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

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

1 OMR路由

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

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

1.1 FSS階段

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

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

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

接下來以圖1為例，分析這兩個算法的具體的實施過程。

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

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

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

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

1.2 DD階段

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

(1)

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

1.3 OMR路由流程

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

圖3 OMR算法流程圖

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

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

(c) 節(jié)點3將復本傳輸至節(jié)點6

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

2 性能仿真

2.1 仿真環(huán)境

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

表3 仿真參數(shù)

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

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

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

2.2.1 目的節(jié)點數(shù)對算法性能的影響

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

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

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

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

圖6 傳輸時延

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

圖7 消息復本數(shù)

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

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

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

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

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

圖9 傳輸時延

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

圖10 消息復本數(shù)

2.2.3 源節(jié)點數(shù)對算法性能的影響

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

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

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

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

圖12 消息復本數(shù)

3 結(jié) 語

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

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