一種基于能效的多擺渡組播路由算法*

莫媛淇，楊文忠，張振宇

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

0 引 言

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

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

1 網絡模型與假設

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

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

圖中，?為擺渡節點，○為普通節點，●為中繼節點。

圖1 網絡拓撲結構Fig 1 Network topology structure

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

2 能量組播樹的構建

2.1 問題定義

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

2.2 能量模型

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

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

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

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

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

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

2.3 能量組播樹

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

2.3.1 組播樹的構建

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

表1 區域狀態表Tab 1 Region state table

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

輸入:源區域，目的區域集合

輸出:源區域到目的區域的能效組播樹

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

2)Dirkstra(Rn);更新各個區域能量優先級

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;∥在鄰居區域中選擇level 最大的區域作為父區域

11)else if

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

12)then compare(destnum);

∥比較level 相同的區域的鄰居區域包含的目的區域的個數

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

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

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

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

16)return Multicast Tree

2.3.2 組播樹的維護

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

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

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

3 仿真實驗

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

1)數據流量對網絡性能的影響

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

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

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

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

2)區域數量對網絡性能的影響

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

如圖7 所示MFMA 和NRA 兩者的數據交付率均與區域的個數呈反比，這是由于從源區域到各個目的區域經過的中間區域個數的增加，導致數據傳輸時延的增加，使某些數據包不能在其生命周期內被傳送到目的區域，從而降低網絡的數據交付率，而MFMA 保證了源區域到各個目的區域經過的跳數最小，使數據傳輸時延最短，因此，在相同的數據包的生命周期內，MFMA 能使更多的數據包成功傳輸到目的區域。

4 結 論

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

圖7 區域的數量對數據交付率的影響Fig 7 Influence of number of region on data delivery rate

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

［1］ 余旻輝，唐 亮.無線傳感器網絡現狀及應用［C］∥信息通信網絡技術委員會年會文，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，Fei 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］.軟件學報，2004，15(5):660－665.