移動Ａｄ ｈｏｃ中發布／訂閱路由協議的網絡仿真

(北京郵電大學， 北京 100876）

摘 要：通過在Ad hoc多播路由協議(ADMR)中加入發布/訂閱匹配算法，將發布/訂閱中間件與移動Ad hoc網絡相結合，設計出適應發布/訂閱分布式網絡的多播路由協議(PSMR)，中間件使用該協議將發布者的數據分發到相匹配的訂閱者。使用NS2網絡仿真平臺實現了該協議，將其與ADMR進行性能比較，大大減少了網絡中分組轉發次數，提高了網絡效率。

關鍵詞：發布/訂閱；移動自組織網絡；多播路由協議；ADMR；PSMR

中圖分類號：TP393.04文獻標志碼：A

文章編號：1001-3695(2009)04-1450-03

Simulation of publish/subscribe multihop routing in mobile Ad hoc network

WANG Ting-ting，ZHAI Li-dong，MA Xiao-lei，LIU Yuan-an

(Beijing University of Posts Telecommunications， Beijing 100876， China)

Abstract:PSMR(publish/subscribe multihop routing) protocol is designed to adapt the publish/subscribe distributed system by adding the publish/subscribe match algorithm to Ad hoc multicast routing protocol ADMR(adaptive demand-driven multicast routing).PSMR was integrated publish/subscribe middleware and mobile Ad hoc network. The middleware was used PSMR to distribute the publisher’s data to relevant subscribers. This protocol PSMR was simulated by NS2 and compared with ADMR in some performances. Simulation conclusion shows that PSMR can greatly reduce the number of packet transmission and enhance the mobile Ad hoc network overall efficiency.

Key words:publish/subscribe; mobile Ad hoc network; multicast routing protocol; ADMR; PSMR

發布/訂閱(publish/subscribe，pub/sub)系統具有異步、多點通信的特點，為信息的發布者和接收者提供了解耦裝置和選擇性的信息分發路徑，使通信的參與者在空間、時間和控制流上完全解耦，適應高度動態的網絡環境和以數據為中心的網絡路由，在開發大規模分布式系統中日益得到廣泛應用[1]。但是發布/訂閱機制在移動Ad hoc網絡中實現比較困難，主要是因為Ad hoc網絡的網絡拓撲是動態變化的，具有很高的靈活性。隨著移動手提式設備的廣泛使用和分布式系統規模的擴大，pub/sub系統必須在移動的、無線的以及高速動態的環境下工作，因此研究移動及無線環境下pub/sub系統的通信具有迫切的必要性。

Ad hoc網絡環境的多播路由協議可以大致分成兩類[2]:a)基于樹結構的多播路由協議。它們使用了固定網絡中基于樹的組播協議的思想，其特點是在源節點與接收節點之間建立一條路徑，如ADMR[3]、AMRoute[4]、AMRIS［5］。b)基于網格結構的多播路由協議。它們能在傳輸數據時為源與接收者之間提供多條路由，如ODMRP[6]、CAMP[7]、DRMR[8]。

將發布/訂閱中間件應用在移動Ad hoc網絡上，目前國際上也有一些成果。STEAM[9]是用于無線Ad hoc網絡的基于事件的中間件；GREEN[10]是一種能夠支持普遍計算應用的發布/訂閱中間件方案，該方案可以支持異構網絡和異構設備；EMMA[11]是JMS在Ad hoc網絡中的應用。



由于移動Ad hoc網絡的動態拓撲特性，要在其上實現發布/訂閱中間件，就必須尋找一種可靠的路由算法。筆者對ADMR協議作了改進，提出了一種新的適用于發布/訂閱中間件的網絡層協議PSMR[12，13]，文獻[12，13]從理論的角度詳細論述了該協議。本文從仿真實現的角度，以ADMR協議為基礎，在其上增加了支持發布訂閱特性的模塊，在網絡仿真平臺NS2上模擬實現了PSMR協議，并且對ADMR和PSMR兩個協議進行了性能仿真與比較。

1 發布/訂閱系統與多播路由協議的結合

發布/訂閱系統是一種使分布式系統中的各參與者，能以發布/訂閱的方式進行交互的中間件系統。在發布/訂閱系統中，信息的生產者和消費者之間所交互的信息被稱為事件。發布者將事件發送給發布/訂閱中間件，訂閱者則向發布/訂閱中間件發出一個訂閱條件，表示對系統中的哪些事件感興趣，如果不再感興趣，也可以取消訂閱。而發布/訂閱中間件則保證將發布者發布的事件及時、可靠地傳送給所有對該事件感興趣的訂閱者。匹配算法負責高效地找到與給定的事件相匹配的所有訂閱條件；而路由算法負責選擇適當的路徑，將一個事件從發布者傳送給訂閱者。



分布式發布/訂閱系統中的信息分發與網絡組播集群類似， 發布/訂閱機制對應于Ad hoc網絡中的多播機制。在發布訂閱多跳網絡中，中間件使用多播路由協議將數據分發到相應的訂閱者那里。發布者如同組播集群源 ，將信息傳遞給多個訂閱者，即組播集群接收者。

在Ad hoc網絡中的多播協議中，當信源需要給某個多播組發布信息數據時，只需將數據發布到該多播組對應的多播組地址中，這樣相應的信宿就會接收到多播信息。在發布/訂閱中間件中，多播地址的概念就轉換為主題的概念。數據發布者將具有指定主題的數據信息發布到網絡中，而需要指定主題信息的訂閱者能夠接收該數據。

2 多播協議ADMR

ADMR是一種基于樹的按需組播路由協議，它盡可能地減少任何非按需成分。每個組播數據包從發送者到接收者沿著設置成組播轉發狀態的最小延遲路徑進行轉發。針對網絡中節點移動或無線傳輸條件的變化，接收者動態地適應發送者的發送模式，以有效平衡開銷。ADMR有一個很重要的特點，就是接收節點可以主動加入多播組。

2.1 ADMR協議報頭格式

ADMR協議是按需路由協議，沒有周期性地控制報文，所以ADMR的每個數據分組報頭都攜帶有控制信息，插入在IP報頭之后。ADMR協議報頭分為固定部分和選項部分，結構如圖1所示。其中固定部分包含在所有ADMR報頭中。

Payload length：指出ADMR報頭的長度，不包括固定部分。這個值定義了ADMR中攜帶的所有選項的總長度。

Options ：可變長度域。它的長度由payload length指出。包含0或者更多塊選項信息。

ADMR協議定義了如下選項[3]：

-Source Information Option

-Receiver Join Option

-Multicast Solicitation Option

-Repair Notification Option

-Reconnect Option 

-Reconnect Reply Option

-Multicast Group Address Option

Multicast Sender Address Option

-Pad1 Option 

-PadN Option 

2.2 ADMR協議原理

ADMR協議多播狀態的建立可以通過信宿發現和信源發現兩種方式[3]。本文主要使用信源發現方式。

當節點R上有一個應用要求加入多播組G時，作為接收節點的R主動在全網洪泛multicast-solicitation分組。任一針對多播組G的源節點S接收到multicast-solicitation分組，都回復該分組，告之R其是組G的發送者。節點R收到multicast-solicitation分組的回復時，單播一個receiver-join分組給源節點S，生成〈S，G〉的轉發狀態，將自己連接到該組和源的多播轉發樹中。源節點生成組內的多播數據包在轉發樹之間洪泛，轉發節點收到數據包，根據receiver-join分組形成的反向路由將包轉發到接收節點。

與Ad hoc中其他多播路由協議相比較，ADMR協議是一種按需路由協議，使得協議開銷較小，路由選擇最小延遲路由，無須單播路由協議的支持，具有一定的有效性和可擴展性，更適合應用在發布/訂閱系統中。但是，ADMR協議直接應用在發布/訂閱系統中是有缺陷的。ADMR協議在本質上來說是屬于通道過濾或主題過濾的范疇，按照主題的不同劃分多播組，而且只是采用惟一的多播地址而不是通道或主題形成的多播轉發網格。在網絡中主題數量很大時，該協議所要求的節點的存儲能力很大，且會出現大量重復存儲，多播路由的選擇也變得非常復雜，不易實現。

在這種情況下，本文提出了一種發布訂閱多跳路由協議，用PSMR來表示。PSMR協議是在ADMR協議基礎上進行改進，解決了上述問題，使其更適于發布/訂閱系統。

3 發布訂閱多跳路由協議PSMR

3.1 PSMR協議報頭格式

PSMR協議的報頭是在ADMR協議報頭中加入了發布/訂閱機制所需的信息，即在源節點的通知分組中的source information option選項中加入發布屬性信息；在接收節點的多播請求分組中，除multicast solicitation option 選項外，增加一種新的選項，即訂閱選項，用來儲存訂閱屬性信息。訂閱選項格式如圖2所示。

3.2 PSMR協議原理

該協議主要是將路由層的多播協議ADMR與中間件層的發布/訂閱機制結合，其路由建立的策略與ADMR協議基本一致，區別在于[12，13]：

a)在每個發布節點（源節點）處增加了發布過濾機制。發布過濾（pub filter）表示發布者對發布信息的約束，其約束條件即屬性，在通知分組中描述。只有與發布過濾相匹配的發布信息才可以被成功發布。

b)在每個訂閱節點（接收節點）處增加了訂閱過濾機制。訂閱過濾表示訂閱者對所要訂閱信息的約束，其約束條件在多播請求分組中描述。只有與訂閱過濾相匹配的發布信息才可以被訂閱者成功收到。

c)在每個轉發節點處增加了訂閱屬性登記表，記錄所有經過它轉發的訂閱者的地址和各自的訂閱屬性。

d)在每個轉發節點處增加了網格節點過濾機制，以適應發布訂閱的具體要求。該機制利用節點處的訂閱屬性登記表，通過添加匹配函數來實現。匹配函數實現發布信息分組和轉發節點的訂閱屬性登記表中屬性條目之間的匹配。當發布者發布信息分組時，只有滿足匹配條件的分組才能夠繼續向前洪泛，而不滿足條件的分組則被網格節點丟棄。網格節點過濾可以減少無效數據在無線Ad hoc網絡的轉發次數，從而減少了發布信息在網絡中的資源占用，提高了網絡的資源占有率。

3.3 PSMR協議代碼實現

3.3.1 主要數據結構

1)發布訂閱消息的屬性定義

enum attribute{A，B，C，D，E}

2)訂閱選項定義

typedef struct{/*訂閱過濾選項*/

#define SUB_OPTION_SIZE32 /*該選項大小*/

int valid_;/*valid_=1，則該選項有效*/

attribute attr;/*訂閱過濾屬性*/

}sub_option;

3)訂閱屬性的存儲

在每個節點處定義了一個數據結構SFTable(表1)，以實現節點處的網格過濾機制。

3.3.2 主要函數

PSMR協議代碼只要實現數據分組的發布、訂閱與接收，包括source information option、receiver join option、multicast solici-tation option等各種選項內容的寫入、讀出與處理；狀態表的寫入與讀出等。PSMR協議優于ADMR協議，更適合發布訂閱網絡，其關鍵在于增加了匹配函數。匹配函數用來作發布屬性與訂閱屬性的匹配運算，匹配成功的數據分組繼續在轉發樹中轉發，匹配失敗的數據分組則被丟棄。

本文在實現PSMR協議時，匹配函數定義如下：

intMulticastState::match(int src_id， attribute pubattr){

SFTable *temp = NULL;/* 訂閱屬性存儲指針 */

SFTableEntry *temp2 = NULL;

int m=0; /* 定義并初始化一個匹配成功標記量 */

temp=sf_table; /* 初始化指針，指向列表的第一個元素 */

while(temp) {

temp2=temp->table_entry;

while(temp2) {

if(temp2->attr == pubattr){

/*若列表中的屬性與發布屬性一致 */

FILE* file = fopen(\"output.txt\"，\"a\"); /* 輸出信息 */

fprintf(file，\"match success\\");

fclose(file); 

int gid = temp->sub_id;

ForwarderState* addFwdTableEntry(int gid，int src_id);

/*匹配成功，則轉發數據分組*/

m=1;/* 匹配成功標記量置1 */

break;

}else {

temp2=temp2->next;

/*匹配不成功，則指針指向下一元素*/

FILE* file=fopen(\"output.txt\"，\"a\");

fprintf(file，\"match failed\\");

fclose(file);

m=0;/* 匹配成功標記量置0 */

}

}

if(m==1) {

FILE* file = fopen(\"output.txt\"，\"a\");/* 輸出標記量 */

fprintf(file，\"m=1\\");

fclose(file); 

break;

} else { 

FILE* file = fopen(\"output.txt\"，\"a\");

fprintf(file，\"m=0\\");

fclose(file);

temp=temp->next;

/*匹配失敗，指針指向下一節點登記條目*/

}

}

if(m==1){

return SUCCESS; 

} else {

return FAILURE;

}

}

4 NS2仿真分析

仿真平臺：NS2

仿真環境參數設置如表2所示。

表1 訂閱屬性存儲結構SFTable

node_1（訂閱節點ID）

node_1的訂閱屬性1

node_1的訂閱屬性2

node_1的訂閱屬性3

node_2

node_2的訂閱屬性1

node_2的訂閱屬性2

node_2的訂閱屬性3

node_3

node_3的訂閱屬性1

node_3的訂閱屬性2

node_4node_4的訂閱屬性1

……

表2 仿真環境參數設置

參數數值

節點個數(n)100

仿真環境(m)1 200×800

節點移動模型隨機點過程

節點移動速度(m/s)可變值，最大20

每個group中發布者個數3

group數目3

為簡化程序設計，突出協議性能方面的比較，本文采用枚舉類型設計發布和訂閱的信息屬性，將信息屬性設為{A，B，C，D，E}五種；采用二維數組類型設計每個轉發節點處的訂閱屬性登記表。當節點收到發布者發布的數據包時，提取其中的發布信息屬性，遍歷本地訂閱屬性登記表，將其元素與發布信息屬性進行比較，當發布信息屬性包含于訂閱屬性時，繼續轉發該數據包，否則丟棄該數據包。PSMR仿真時序如圖3所示。

ADMR與PSMR包的轉發次數比較如圖4所示。由圖4可以看出，由于增加了網格過濾機制，將發布訂閱匹配算法結合在多播路由協議中， PSMR協議的包轉發次數要遠小于ADMR協議的包轉發次數，這樣可以極大地減少無用的數據傳送，同時減少能量的消耗，極大地提高了網絡效率和網絡的整體生存時間。ADMR與PSMR信息傳送概率比較如圖5所示。由圖5可以看出，由于使用相同的路由策略，ADMR協議和PSMR協議在信息傳送概率上是基本一致的，但是由于過濾機制的使用，PSMR協議的信息傳送概率略低于ADMR協議。

5 結束語

本文將發布訂閱機制與移動Ad hoc網絡的多播路由協議ADMR相結合，設計出適應發布訂閱的多播協議PSMR，建立了發布訂閱多跳網絡。PSMR采用了發布過濾、訂閱過濾和網格過濾機制，當分發信息在多播網格中進行轉發時，中間節點需要使用網格節點過濾對數據進行匹配判決，是繼續進行網格洪泛還是銷毀分發信息。因此，與ADMR協議相比，網絡中包的轉發次數大大減少。筆者還將繼續對PSMR協議作進一步改進，結合QoS算法，使得發布訂閱多跳路由協議更加完善。

參考文獻：

［1］

EUGSTER P T，FELBER P A，GUERRAOUI R，et al.The many faces of publish/subscribe [J].ACM Computing Surveys，2003，35(2):114-131.

[2]周元，李光勝，詹永照，等.三種Ad hoc網絡組播協議的性能分析與比較[J].計算機科學，2006，33（10）:40-48.

[3]JETCHEVA J G，JOHNSON D B.Adaptive demand-driven multicast routing in multi hop wireless Ad hoc networks[C]//Proc of Mobihoc.Long Beach，CA:[s.n.]，2001:33-44.

[4]XIE J，ROUTE A M.Ad hoc multicast routing protocol[J].Mobile Networks and Applications，2002，7(6):429-439.

［5］ WU C W， TAY Y C.AMRIS:a multicast protocol for Ad hoc wireless networks[C]//Proc of IEEE Military Communications Conference.Atlantic City：[s.n.]，1999：25-29.

[6]LEE S J，GERLA M，CHIANG C C.On-demand multicast routing protocol in multi hop wireless mobile networks[J].Mobile Networks and Applications，2002，7(6):441-453.

[7]GARCIA-LUNA-ACEVES J J， MADRUGA E L.Core-assisted Mesh protocol[J].IEEE Journal on Selected Areas in Communications，1999，17(8):1380-1394.

[8]ZHOU Yuan，LI Guang-sheng，ZHAN Yong-zhao，et al.DRMR:dynamic-ring-based multicast routing protocol for Ad hoc networks[J].Journal of Computer Science Technology，2004，19(6):909-919.

[9]MEIER R，CAHILL V.Steam:event-based middleware for wireless Ad hoc networks[C]//Proc ofthe 22nd International Conference on Distributed Computing Systems.2002:639-644.

[10]SIVAHARAN T，BLAIR G，COULSON G.GREEN: a configurable and re-configurable publish-subscribe middleware for pervasive computing [C]//Proc ofDistributed Objects and Applications.Agia Napa， Cyprus:[s.n.]，2005:732-749.

[11]MUSOLESI M，MASCOLO C，HAILES S.Adapting asynchronous messaging middleware to Ad hoc networking [C]//Proc of the 2nd Workshop on Middleware for Pervasive and Ad hoc Computing.2004:121-126.

[12]ZHAI Li-dong，MA Xiao-lei，GAO Jin-chun，et al.PSMR:publish/subscribe multi-cast routing for wireless Ad hoc networks[C]//Proc of International Conference on Computational Intelligence and Security. Harbin:IEEE Computer Society，2007:554-557.

[13]ZHAI Li-dong，LIU Yuan-an，MA Xiao-lei，et al.Research of publish/subscribe paradigm for mobile Ad hoc networks [J].Journal of Beijing University of Posts and Telecommunications，2008，31(2):30-34.