莫媛淇，楊文忠，張振宇

(新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊830046)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是部署在檢測區(qū)域內(nèi)由大量廉價的微型傳感器節(jié)點構(gòu)成分布式自組網(wǎng)絡(luò)，這些節(jié)點能夠?qū)崿F(xiàn)傳感、計算和無線通信功能，但也受到能量和帶寬的限制［1，2］。因此，基于能量的路由設(shè)計在無線傳感器網(wǎng)絡(luò)路由機制的研究中變得日趨重要。目前，針對無線傳感器網(wǎng)絡(luò)的組播問題，研究學(xué)者們提出了多種路由策略［3］，根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的不同，可將其分為兩類:基于樹形結(jié)構(gòu)的方法和基于網(wǎng)格結(jié)構(gòu)的方法?；跇湫谓Y(jié)構(gòu)的路由協(xié)議主要包括VLMM［4］，EMRS［5］和GMR［6］等。這類協(xié)議利用不同的能量啟發(fā)式構(gòu)造組播樹，根據(jù)組播樹提供的最優(yōu)路徑可以把信息快速準確地發(fā)送到目的節(jié)點，但基于組播樹的網(wǎng)絡(luò)魯棒性較差容易產(chǎn)生孤立節(jié)點。基于網(wǎng)格結(jié)構(gòu)的路由協(xié)議主要包括E2MRP［7］，DCMP［8］等。這類路由協(xié)議在網(wǎng)格建立的基礎(chǔ)上，選取一組中繼節(jié)點完成組播分組的傳送，使源和目的節(jié)點之間存在多條路徑，能很好地適應(yīng)節(jié)點的移動性，解決了樹形結(jié)構(gòu)引起的單點失效的問題，但在網(wǎng)格內(nèi)信息的洪泛將產(chǎn)生巨大的能耗。

針對節(jié)點能量受限且通信間斷等問題，本文提出多擺渡組播路由算法(multiple ferries multicast routing algorithm，MFMA)。該算法在網(wǎng)絡(luò)區(qū)域劃分的前提下，利用區(qū)域擺渡節(jié)點和區(qū)間中繼節(jié)點的交互實現(xiàn)網(wǎng)絡(luò)的連通，在此基礎(chǔ)上，MFMA 提出了區(qū)域能量優(yōu)先級，并基于此能量優(yōu)先級，選擇合適的中間區(qū)域，以確定能量最優(yōu)的組播樹，最后各個區(qū)域內(nèi)的擺渡節(jié)點根據(jù)此組播樹的路徑信息完成組播數(shù)據(jù)的傳遞。

1 網(wǎng)絡(luò)模型與假設(shè)

在圖1 所示網(wǎng)絡(luò)拓撲結(jié)構(gòu)中，將節(jié)點均勻分布的網(wǎng)絡(luò)G 劃分為M 個相等的區(qū)域，那么，每個小區(qū)域Ri中分布著N/M 個節(jié)點(總節(jié)點個數(shù)為N)和一個擺渡節(jié)點f。相鄰的區(qū)域利用中繼節(jié)點Nr來中繼區(qū)間信息。為了方便描述，本文將中繼節(jié)點Nr虛擬化為區(qū)域間的通信鏈路，網(wǎng)絡(luò)為以區(qū)域R 為傳輸單元的無向連通圖G(R，Nr)，如圖2 所示。其中R={R1，R2…Rd}表示網(wǎng)絡(luò)所有區(qū)域的集合，其中每個區(qū)域中又由若干節(jié)點組成，即Ri={1 ＜j ＜N/M|Nj}，Nr={Ri≠Rj|Nr(Ri，Rj)}為網(wǎng)絡(luò)中繼節(jié)點集合，即通信鏈路的集合。任何區(qū)域間最多有一條鏈路，若區(qū)域Ri，Rj∈R 且Ri，Rj間存在一條直接相連的鏈路，記此鏈路為Nr(Ri，Rj)。

本文將源節(jié)點所在的區(qū)域稱為源區(qū)域記為Rs，目標節(jié)點所在區(qū)域稱為目的區(qū)域，記為Rd，與區(qū)域有邊直接相連的區(qū)域稱為該區(qū)域的鄰居區(qū)域，若Ru是Rv的鄰居區(qū)域，則Ru∈Neighbor(Rv)且存在Nr(Ru，Rv)。每個區(qū)域有自己的屬性AtRi=(［Di］，［hi］)，其中，Di為區(qū)域的度，表示與該區(qū)域相關(guān)聯(lián)的邊的個數(shù)，用該區(qū)域鄰居區(qū)域的個數(shù)表示，hi表示當前區(qū)域到達源區(qū)域的最小跳數(shù)，用當前區(qū)域到達源區(qū)域的最短路徑上經(jīng)過的中間區(qū)域的個數(shù)表示。

圖中，?為擺渡節(jié)點，○為普通節(jié)點，●為中繼節(jié)點。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig 1 Network topology structure

圖2 無向連通圖Fig 2 Undirected connected graph

2 能量組播樹的構(gòu)建

2.1 問題定義

基于上述網(wǎng)絡(luò)模型，本文主要研究在指定源區(qū)域Rs和目的區(qū)域集合Rd，Rd={Rd1，Rd2，…，Rdk}(k ＜M)的情況下，尋找一棵以Rs為根并且可以到達所有目的區(qū)域Rd的樹，使該組播樹滿足在時延受限的條件下總能耗最小。

2.2 能量模型

本文假設(shè)普通節(jié)點和中繼節(jié)點具有相同的初始能量和發(fā)射功率，擺渡節(jié)點沒有能量限制。根據(jù)節(jié)點能量消耗和通信模型，節(jié)點發(fā)送和接收k bit 數(shù)據(jù)的能耗分別為

其中，Eelec為電路上接收或發(fā)送每比特數(shù)據(jù)消耗的能量，εfs為電路放大器系數(shù)，d 為擺渡節(jié)點與普通節(jié)點的通信距離，a 為路徑損耗指數(shù)，滿足關(guān)系2 ＜a ＜4。根據(jù)文獻［10］能量消耗與通信距離存在如下關(guān)系

由于擺渡節(jié)點與普通節(jié)點只發(fā)生近距離的數(shù)據(jù)傳輸，假定該通信距離一定，根據(jù)式(3)可知，擺渡節(jié)點與任意節(jié)點通信的能耗相同，那么組播樹的能量消耗與參與通信的節(jié)點的個數(shù)呈正比。在本文提出的網(wǎng)絡(luò)模型中，由于度大的區(qū)域可以承擔更多的中繼任務(wù)，起到減少組播樹中參與通信的節(jié)點的個數(shù)的目的，因此，選擇度大的區(qū)域作為中繼區(qū)域可以有效的減少能量的消耗。

綜上，區(qū)域能量優(yōu)先級level 度量公式，如式(4)所示

其中，區(qū)域度Di可以控制組播樹的能量消耗

由于最小跳數(shù)hi可以控制單個數(shù)據(jù)的傳輸時延［11］，因此，level 的值越大，表示選擇的中間區(qū)域能使組播樹能量消耗越少且傳輸時延越短。

2.3 能量組播樹

在設(shè)計區(qū)域組播樹時，采用貪婪算法思想，迭代選擇鄰居區(qū)域中能量優(yōu)先級level 最高的作為中繼區(qū)域。組播成員的加入和離開通過控制信息的交互實現(xiàn)，其中孩子請求信息(child request message，CRM)和回復(fù)孩子請求信息(reply child request message，RCRM)協(xié)助組播成員區(qū)域加入組播樹，離開請求信息(left request message，LRM)和回復(fù)請求信息(reply left request message，RLRM)實現(xiàn)區(qū)域離開組播樹，在RCRM 中包含目的區(qū)域到源區(qū)域的路徑信息Path。RCRM 在組播樹的構(gòu)建中是動態(tài)變化的。另外，每個區(qū)域的擺渡節(jié)點維護區(qū)域的狀態(tài)信息表StaTable，如表1。當父親區(qū)域請求孩子區(qū)域時，父親區(qū)域?qū)顟B(tài)信息表StaTable封裝在CRM 頭部一同發(fā)送給鄰居區(qū)域，接收到CRM 的區(qū)域便可據(jù)此獲悉鄰居區(qū)域的能量優(yōu)先級。

2.3.1 組播樹的構(gòu)建

算法主要描述了以區(qū)域為單位的能量組播樹的構(gòu)建方法，其中，1 ～3 行是初始化階段，利用Dirkstra 算法，更新各區(qū)域到源區(qū)域的最小跳數(shù)hi，并根據(jù)式(5)更新區(qū)域的度Di及各區(qū)域的鄰居列表Neighbor.list;4 ～16 行是組播樹構(gòu)建階段算法從源區(qū)域開始向flag=0 鄰居區(qū)域發(fā)送孩子請求信息CRM。若Ri是目的區(qū)域，在Rd［］中刪除Ri，并根據(jù)式(4)計算接收到的CRM 中的區(qū)域level，選擇level 最大的區(qū)域作為父親區(qū)域，當多個鄰居區(qū)域的level 相同時，選擇本身是目的區(qū)域或者其鄰居區(qū)域中包含目的區(qū)域的區(qū)域作為父親區(qū)域，將該父親區(qū)域加入組播樹，并將路徑信息追加到RCRM 中回復(fù)該父親區(qū)域，其余的區(qū)域放在備用父區(qū)域列表中，該父親區(qū)域再以同樣的方式尋找自己的父親區(qū)域直到Rd［］為空，說明所有的目的區(qū)域已經(jīng)加入組播樹算法結(jié)束，此時，源從收到的RCRM 中可獲悉各個目的區(qū)域到達自己的最佳路徑信息。

表1 區(qū)域狀態(tài)表Tab 1 Region state table

算法1 construct multicast tree(Rs，Rd［］)

輸入:源區(qū)域，目的區(qū)域集合

輸出:源區(qū)域到目的區(qū)域的能效組播樹

1)level=0，flag=0;∥初始化能量優(yōu)先級和表示符

2)Dirkstra(Rn);更新各個區(qū)域能量優(yōu)先級

3)renew Stable.level and Stabel.Neighbor.list();

4)Multicast Tree add Rsand Rd［］;

5)For each Riin RN

6)while(Rd［］! =null) do

7)Risend CRM(Stable) to Ri.neighbor.list();

8)For any Rp，Rq∈Rj.neighbor.list()

9)if(Rp.level=max{Rj.neighbor.level})

10)Rj.parent→Rp;Multicast Tree add Rp;∥在鄰居區(qū)域中選擇level 最大的區(qū)域作為父區(qū)域

11)else if

Rp.level=Rq.level=max{Rj.neighbor.level})

12)then compare(destnum);

∥比較level 相同的區(qū)域的鄰居區(qū)域包含的目的區(qū)域的個數(shù)

13)If(Rp.neb.list().destnum ＞Rq.neb.list().destnum)

14)Rj.parent→Rp; Multicast Tree add Rp;

∥選擇本身是目的區(qū)域或者其鄰居中包含目的區(qū)域多的區(qū)域作為父區(qū)域

15)else Re-parent.list add Rp;∥其余鄰居區(qū)域加入備用父親區(qū)域

16)return Multicast Tree

2.3.2 組播樹的維護

當有區(qū)域要離開組播樹時，若該區(qū)域不存在孩子區(qū)域，則直接向父親區(qū)域發(fā)送LRM;否則，向孩子區(qū)域發(fā)送LRM，孩子區(qū)域從備用父親區(qū)域列表中選擇level 次高的作為父親區(qū)域建立通信，并向原父親區(qū)域回復(fù)RLRM，接收到回復(fù)后，該區(qū)域再向父親區(qū)域發(fā)送LRM，并斷開連接處于休眠狀態(tài)。

當有區(qū)域要加入時，從收到的CRM 中選擇level 最大的區(qū)域作為父親區(qū)域，此過程與建樹過程類似，這里不再贅述。

當源區(qū)域R2產(chǎn)生到Rd={R6，R7，R8}數(shù)據(jù)包時按著算法1 的構(gòu)建過程，便可得到如圖3(a)所示的組播樹。而基于NRA［12］方法可得到如圖3(b)的組播樹，基于最短路徑樹的構(gòu)建方法［13］可得到如圖3(c)的組播樹，從能量的角度分析，圖3(a)中的組播樹使更多的區(qū)域處于休眠狀態(tài)，相應(yīng)的能量消耗最少。因此，本文提出的組播樹的構(gòu)建是在控制時延的基礎(chǔ)上能量高效的。

3 仿真實驗

本文利用MyEclipce8.0 編程實現(xiàn)仿真任務(wù)，通過改變網(wǎng)絡(luò)數(shù)據(jù)流量和區(qū)域個數(shù)，對NRA，MFMA 的網(wǎng)絡(luò)平均傳輸能耗和數(shù)據(jù)交付率進行了比較分析。仿真參數(shù)配置為:網(wǎng)絡(luò)大小12 km×12 km;數(shù)據(jù)包的大小512 字節(jié)，接收或發(fā)送每比特數(shù)據(jù)的能耗5×10－8J，功率放大器εfs=10(pJ/bit/m2)，擺渡節(jié)點和普通節(jié)點的通信半徑均為150 m;節(jié)點的初始能量E0=50 J。

1)數(shù)據(jù)流量對網(wǎng)絡(luò)性能的影響

在區(qū)域個數(shù)M=9 時，圖4、圖5 分別顯示了網(wǎng)絡(luò)數(shù)據(jù)流量對平均傳輸能量和數(shù)據(jù)交付率的影響。如圖4 所示，隨著網(wǎng)絡(luò)中數(shù)據(jù)流量的增加，MFMA 的平均能量消耗明顯低于NRA，這是因為MFMA 是基于區(qū)域局部信息進行建樹的，在建樹過程中利用貪婪的算法思想使組播樹中包含的中間區(qū)域最少，從而更多的區(qū)域處于休眠狀態(tài)，避免了額外的能量消耗。

如圖5 所示，隨著網(wǎng)絡(luò)中數(shù)據(jù)流量的增加，MFMA 和NRA 兩種方法的數(shù)據(jù)交付率在不斷降低，這是因為節(jié)點的初始能量有限，當執(zhí)行了一定量的通信任務(wù)后，由于節(jié)點能量的不足使部分通信鏈路失效，從而導(dǎo)致數(shù)據(jù)交付率的降低;在NRA 中，源到目的只存在一條路徑，關(guān)鍵路徑上節(jié)點失效的問題將嚴重影響數(shù)據(jù)的交付率，而MFMA 中，源到目的存在多條路徑，有效緩解了上述問題，增加了網(wǎng)絡(luò)生命周期，因此，MFMA 的數(shù)據(jù)交付率明顯高于NRA。

圖4 數(shù)據(jù)流量對平均傳輸能量的影響Fig 4 Influence of data flow on average transmission energy

圖5 數(shù)據(jù)流量對數(shù)據(jù)交付率的影響Fig 5 Influence of data flow on data pay rate

2)區(qū)域數(shù)量對網(wǎng)絡(luò)性能的影響

在網(wǎng)絡(luò)信息產(chǎn)生率為5 000 條/min 的情況下，圖6 和圖7分別顯示了網(wǎng)絡(luò)中包含的區(qū)域數(shù)量對平均傳輸能量和數(shù)據(jù)交付率的影響，如圖6 所示，MFMA 和NRA 兩者的平均傳輸能耗均與區(qū)域的個數(shù)呈正比，這是由于伴隨著網(wǎng)絡(luò)中區(qū)域個數(shù)增加，從源區(qū)域到各個目的區(qū)域經(jīng)過的中間區(qū)域的個數(shù)也在增加，因此，產(chǎn)生了更多的通信量，導(dǎo)致了網(wǎng)絡(luò)平均能耗的增加。而在同等條件下，MFMA 的平均能量消耗低于NRA。

如圖7 所示MFMA 和NRA 兩者的數(shù)據(jù)交付率均與區(qū)域的個數(shù)呈反比，這是由于從源區(qū)域到各個目的區(qū)域經(jīng)過的中間區(qū)域個數(shù)的增加，導(dǎo)致數(shù)據(jù)傳輸時延的增加，使某些數(shù)據(jù)包不能在其生命周期內(nèi)被傳送到目的區(qū)域，從而降低網(wǎng)絡(luò)的數(shù)據(jù)交付率，而MFMA 保證了源區(qū)域到各個目的區(qū)域經(jīng)過的跳數(shù)最小，使數(shù)據(jù)傳輸時延最短，因此，在相同的數(shù)據(jù)包的生命周期內(nèi)，MFMA 能使更多的數(shù)據(jù)包成功傳輸?shù)侥康膮^(qū)域。

4 結(jié) 論

圖6 區(qū)域的數(shù)量對平均傳輸能量的影響Fig 6 Influence of number of region on average transmission energy

圖7 區(qū)域的數(shù)量對數(shù)據(jù)交付率的影響Fig 7 Influence of number of region on data delivery rate

為實現(xiàn)在節(jié)點通信間斷的無線傳感器網(wǎng)絡(luò)環(huán)境中的組播路由機制，本文提出一種MFMA。該算法區(qū)域劃分的基礎(chǔ)上，引入軌跡可控的區(qū)域擺渡節(jié)點負責區(qū)域內(nèi)信息的傳輸，區(qū)域間的共享節(jié)點負責信息的中繼。為了降低通信能耗，該算法提出了區(qū)域能量優(yōu)先級，并利用貪婪算法的思想根據(jù)區(qū)域優(yōu)先級構(gòu)建以區(qū)域為傳輸單位的能量組播樹，保證總能耗最小，而鄰居區(qū)域的優(yōu)先級是通過控制信息的交互獲得的，這樣就避免了周期性廣播自身信息的能量消耗，當組播樹中有節(jié)點失效時，MFMA 可從后備中繼列表中選擇合適的中繼替代該失效節(jié)點，以保證通信鏈路的連通。仿真結(jié)果表明了該算法在能量和傳遞率等方面的有效性。

［1］ 余旻輝，唐 亮.無線傳感器網(wǎng)絡(luò)現(xiàn)狀及應(yīng)用［C］∥信息通信網(wǎng)絡(luò)技術(shù)委員會年會文，2011:1396－1403.

［2］ Chen C，Chen Z.Evaluating contacts for routing in highly partitioned mobile networks［C］∥Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking，ACM，2007:17－24.

［3］ Mongiovi M，Singh A K，Yan X，et al.Efficient multicasting for delay tolerant networks using graph indexing［C］∥2012 Proceedings IEEE INFOCOM，IEEE，2012:1386－1394.

［4］ Anmol S，Brian S，Richard Han.VLM2:A very light weight mobile multicast system for wireless sensor networks［C］∥Proceedings of the IEEE Wireless Communications and Networking Conference，2003:1936－1941.

［5］ Niwat T，Yoshito T，Kaoru S.Tree-based data dissemination in wireless sensor networks［J］.Journal of University of Tokyo Center for Spatial Information Science(CSIS)，2005(2):17－18.

［6］ Sanchez J A，Ruiz P M，Liu Jennifer，et al.bandwidth-efficient geographic multicast routing protocol for wireless sensor networks［J］.IEEE Sensor Journal，2007，7(5):627－636.

［7］ Song W Z，Wang Y，Li X Y，et al.Localized algorithms for energy efficient topology in wireless Ad Hoc networks［J］.Mobile Networks and Applications，2005，10(6):911－923.

［8］ Lee S J，Williams Mario G.Ad Hoc wireless multicast with mobility prediction［C］∥Proc of Mobile Networks and Applications Conf，2001:351－360.

［9］ Zeng Guokai，Wang Chen，Li Xiao.Grid multicast:An energy efficient multicast algorithm for wireless sensor networks［C］∥Proc of Fourth IEEE International Conference on Networked Sensing Systems，Braunschweig，2007:267－274.

［10］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Hawaii International Conference on System Science，Hawaii，USA，2000:10－20.

［11］Zhang Z，F(xiàn)ei Z M.Route design for multiple ferries in delay tolerant networks［C］∥Proceedings of Wireless Communication and Networking Conference，Kowloon，China，2007:3460－3465.

［12］Zhao W，Ammar M，Zegura E.Controlling the mobility of multiple data transport ferries in a delay-tolerant network［C］∥Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies，2005:1407－1418.

［13］王 濤，李偉生.低代價最短路徑樹的快速算法［J］.軟件學(xué)報，2004，15(5):660－665.