基于位置感知的高效發布/訂閱路由算法

任 智，張 勇，彭 晨，武 楊

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

基于位置感知的高效發布/訂閱路由算法

任 智，張 勇，彭 晨，武 楊

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

針對現有結合地理位置信息的移動Ad hoc（自組織）網絡路由算法中節點在更新位置信息和回應請求時增加控制包開銷的問題，提出了一種EPRLM（基于位置感知的移動Ad hoc網絡高效發布/訂閱路由算法）。EPRLM結合基于NFZ（節點轉發區域）的信息更新機制和Join Reply（加入回應）包的捎帶機制，在節點發布內容的過程中，分析位置信息并及時更新，同時適當減少控制包的轉發。

移動自組織網絡；發布/訂閱；內容路由；位置感知

0 引 言

發布/訂閱系統［1］在信息生成和接受兩者間具有弱耦合、非同步及多點通信的特點，成為很多網絡應用的一種重要組件［2］，尤其適用于具有動態拓撲特性的移動Ad hoc（自組織）網絡。

針對移動Ad hoc網絡中基于位置的發布/訂閱路由算法，目前已有一些研究。文獻［3］提出了一種STEAM（基于附近和分布式過濾的區域事件轉發群組算法），在該算法中，訂閱節點只訂閱附近發布方的內容。這導致只能在發布內容時分發內容給目標區域內的節點，限制了內容的發布與匹配。文獻［4］提出了INGEO（基于內部地理位置的路由協議）算法，該算法以速度位移矢量來重新定位移動的訂閱節點。文獻［5］提出了基于位置的自適應路由算法，在合理的區域內實現內容的分發和匹配。但該算法較少考慮節點的移動性，以節點的請求頻次計算的結果因節點頻繁移動而不準確，并且所有節點的區域頻繁更新所帶來的開銷很大。文獻［6］提出的Courier算法（基于位置感知的有效群組通信算法），類似源路由算法LGS（以位置為導向的小區多播生成樹算法）［7］，訂閱節點將速度位置信息嵌在Hello包內，再轉發至內容發布方，依靠訂閱節點及時更新信息，發布方計算發布內容所需轉發的路徑轉發樹和受限泛洪區域的大小，實現目標區域節點的內容匹配。基于上述分析，以Courier算法為代表的基于位置感知的路由算法對于位置速度信息的更新要求頻繁，且Hello包存在冗余廣播問題。本文在文獻［6］的基礎上提出一種EPRLM（基于位置感知的移動Ad hoc網絡高效發布/訂閱路由算法）。本文的主要貢獻有:（1）在內容消息接收過程中，節點通過計算自身是否移出區域來判斷是否更新位置速度信息，從而減少了不必要的控制數據包轉發；（2）訂閱節點的回應包可以捎帶之后的Hello包信息，減少了冗余Hello包的廣播。

1 網絡模型與問題描述

1.1 網絡模型

定義1（節點轉發區域）如圖1所示。在t1時刻，源節點srcA收到訂閱節點memB的位置更新信息；在t2時刻（t2＞t1），srcA發送數據給memB；memB在t1～t2這個時間段內能夠移動的范圍是以srcA存儲的memB位置為中心、半徑為VB（t2-t1）的圓形區域，即NFZ（節點轉發區域）。

圖1 節點轉發區域

定義2（群組轉發區域）如圖2所示。srcA發布內容給多個訂閱節點時，需要優化轉發區域。首先srcA降序排列訂閱節點的NFZ大小，然后判斷NFZC和NFZB的關系。如果二者相交，并且半角α1小于閾值［6］，則合并兩區域；如果兩區域中的一個區域包含另一區域，則將其合并為一個區域；如果兩區域并不包含或者相交，但是半角α1小于閾值［6］，則合并兩區域。至此，形成GFZ（群組轉發區域）。

圖2 群組轉發區域

定義3（歐幾里德Steiner樹）如圖3所示。A、B和C為網絡中的3個節點，S為歐幾里德Steiner節點（即網絡中的虛擬中繼節點）。節點A發送給B和C的總的開銷，可以經過S（實際中也可以是S的附近節點）再分別分發至B和C。而對于多個訂閱節點的GFZ，此時可以通過迭代計算出適合的歐幾里德Steiner樹。

圖3 歐幾里德Steiner樹區域

1.2 問題描述

以Courier算法為代表的基于位置感知的路由算法存在以下問題:

（1）位置速度信息需要通過Hello消息頻繁更新。而在節點沒有離開NFZ時，上次更新的信息依然可以將內容轉發至此區域，并實現區域泛洪，使得節點收到此發布內容。此時，更新導致冗余開銷。

（2）在訂閱節點回應源節點的請求包（Join Request）時，回應包（Join Reply）和之后一次的Hello包所起作用重復，產生冗余。

2 EPRLM

EPRLM采用基于NFZ的信息更新以及Join Reply包的捎帶等新機制，從而達到內容消息與訂閱節點的高效匹配，降低控制開銷的效果。

2.1 EPRLM新機制

2.1.1基于NFZ的信息更新機制

Courier算法只考慮了訂閱節點位置速度信息改變后，通過Hello消息通知發布節點。但是，如果訂閱節點在接收內容消息時并沒有移出NFZ，此時內容消息已經在轉發的路徑上，那么此次位置速度信息的更新就不會起作用，發布節點基于上次的位置速度信息依然可以將消息泛洪至訂閱節點。因此，訂閱節點在接收內容消息時，位置速度信息如果發生變更，首先判斷訂閱節點自身是否移出上次位置速度信息更新到目前為止的NFZ。如果已經移出，則通過Hello包更新位置速度信息，否則，在位置速度信息失效前不再更新。

這種嘗試對職業院校無疑是有幫助的，但對企業來說也存在一些抱怨，如教師對產品開發缺乏經驗導致校企磨合周期很長，效率過低導致公司技術人員對此持消極態度，教師對產品開發過程不熟導致浪費的材料很多，教師對課程資源開發不熟導致占用企業技術人員太多時間，影響公司正常運作。

通過基于NFZ的信息更新，可以減少頻繁轉發至發布節點的信息更新Hello包，從而減少網絡的控制開銷，減緩網絡的通信負荷。

2.1.2 Join Reply包的捎帶機制

在Courier原算法中，訂閱節點收到發布節點的請求包Join Request時，需要回應Join Reply包；并且在回應包到達發布節點的過程中，對應路徑上的節點須轉發此消息。此后，產生或轉發回應包的節點需要廣播Hello包告知鄰居節點自己的狀態信息，而該Hello包的信息與先前回應包的信息重合，產生冗余。本算法提出了Join Reply包的捎帶機制，改變Join Reply包的消息類型并在轉發時廣播此消息，此時除轉發至發布節點路徑上的節點需要繼續廣播此包外，其余節點收到Join Reply包后將其當作Hello包提取信息。

Join Reply包的捎帶機制將訂閱節點至發布節點路徑上所有節點的一次Hello包廣播的信息由Join Reply包捎帶完成，降低了冗余控制開銷，減少了信道資源的競爭。

2.2 算法操作

EPRLM的主要操作步驟如下:

（1）發布節點周期性全網泛洪Join Request包（包含發布節點ID、位置及內容摘要等信息）。

（2）節點收到Join Request包后，如需要發布節點所擁有的內容，則回復Join Reply包（包含該節點ID、位置和速度等信息）并在轉發時廣播此消息，此時除轉發至發布節點路徑上的節點需要繼續廣播此包外，其余節點收到Join Reply包后將其當作Hello包提取信息。

（3）節點收到Join Request包后，如不需要發布節點所擁有的內容，則繼續廣播此消息。

（5）訂閱節點的位置速度發生變化需要更新時，首先判斷訂閱節點自身是否移出上次位置速度信息更新到目前為止的NFZ。如果已經移出，則通過Hello包更新位置速度信息；否則，在位置速度信息失效前不再更新。

3 仿真

本文使用OPNET［8］作為仿真軟件平臺，選取LGS算法和Courier算法作為與EPRLM進行比較的對象，在相同仿真條件下（仿真參數設置如表1所示）分析比較3種算法的消息傳送成功率、消息端到端時延、內容消息轉發次數和控制包開銷等性能。其中，實際的消息端到端時延等于平均跳數乘以每一跳的平均轉發時間，而每一跳的平均轉發時間依賴于具體的硬件條件；內容消息轉發次數為內容消息成功到達所有訂閱節點所需轉發的總次數。

表1 仿真默認參數

（1）消息傳送成功率

3種算法的消息傳送成功率仿真結果如表2所示。從表中可以看出，EPRLM的消息傳送成功率高于Courier和LGS算法，這是因為基于NFZ的信息更新機制減少了Hello包的產生和轉發，而且此時減少的Hello包原本是沿著與內容消息傳播的反方向路徑轉發的，由此減少了沖突和資源競爭。同樣，Join Reply包的捎帶機制也降低了信道中資源的競爭。

表2 3種算法的消息傳送成功率對比

（2）消息端到端時延

3種算法的消息端到端時延仿真結果如圖4所示。由圖可見，EPRLM的消息端到端時延低于Courier和LGS算法，這是因為EPRLM中基于NFZ的位置信息更新機制減少了Hello包的數量，降低了與反方向路徑內容消息的轉發而產生的信道和資源競爭，減少了同一路徑上轉發消息的負擔；另外，Join Reply包的捎帶機制同樣降低了信道中資源的競爭。平均跳數隨網絡中節點數目增加而減少的原因是:在密集網絡中發現源節點到目的節點之間最短路徑的概率會更高一些。

圖4 3種算法的消息端到端時延比較

（3）內容消息轉發次數

在不同節點數時3種算法的內容消息轉發次數比較如圖5所示。從圖中可以看出，隨著節點數的增多，3種算法的內容消息轉發次數都是遞增的。EPRLM的內容消息轉發次數比其他兩種算法低，主要是因為EPRLM的兩種新機制減少了Hello包的產生和轉發，減少了信道資源的競爭和沖突，因而減少了內容消息轉發次數。

圖5 3種算法的內容消息轉發次數比較

（4）控制包開銷

圖6給出了不同節點數下3種算法的控制包開銷的比較。由圖可見，相對于Courier和LGS算法，EPRLM在不同節點數下的控制包開銷都是最少的，這是因為基于NFZ的位置信息更新機制和Join Reply包的捎帶機制都減少了Hello包的產生和轉發，且減少的沖突和資源競爭帶來的控制包開銷的降低也很可觀。

圖6 3種算法的控制包開銷比較

4 結束語

針對結合地理位置信息的發布/訂閱內容路由算法中節點頻繁更新位置信息和控制包存在冗余的問題，本文提出了EPRLM。仿真驗證表明，與Courier和LGS算法相比，EPRLM能夠很好地提高網絡中節點的消息傳送成功率，并降低網絡吞吐量，減少消息時延和發送次數，降低控制開銷。

［1］Carzaniga A，Rosenblum D S，Wolf A L.Design and evaluation of a widearea event notification service［J］.ACM Transactions on Computer Systems，2001，19（3）:332-383.

［2］Rezende G C，Rocha B，Loureiro A.Publish/subscribe architecture for mobile ad hoc networks［C］// Proc of the ACM Symposium on Applied Computing 2008.Fortaleza，Brazil:ACM，2008:1913-1917.

［3］Rene M，Vinny C.On event-based middleware for location-aware mobile applications［C］//IEEE Transactions on Software Engineering 2010.Los Alamitos: IEEE，2010，36（3）:409-430.

［4］Hai L，Houda L.INGEO:indoor geographic routing protocol for MANETs［C］//In Proceedings of the 3rd International Conference on Mobile Computing and U-biquitous Networking 2006.San Jose:ACM，2006: 224-229.

［5］Holzer A，Eugster P，Garbinato B.ALPS-Adaptive Location-based Publish/Subscribe［J］.Computer Networks，2012，56（12）:2949-2962.

［6］Mitra P，Poellabauer C.Efficient group communications in location aware mobile ad-hoc networks［J］.Pervasive and Mobile Computing，2012，（8）:229-248.

［7］Chen K，Nahrstedt K.Effective location-guided tree construction algorithms for small group multicast in MANET［C］//In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies 2002.New York:IEEE，2002:1180-1189.

［8］陳敏.OPNET網絡仿真［M］.北京:清華大學出版社，2004.

Efficient Publish/Subscribe Routing Based on Location Aware

REN Zhi，ZHANG Yong，PENG Chen，WU Yang
（Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

To solve the problem that the nodes updating the location information and respond to requests which increases the control packet overhead in existing content routing based on location aware for mobile Ad hoc networks，an Efficient Publish/ subscribe Routing based on Location aware for Mobile Ad hoc networks（EPRLM）is proposed.Combining information update based on NFZ area mechanism and piggybacking mechanism of join reply packet，EPRLM analyzes the location information and update on time to reduce the control packet forwarding appropriately in the process of publishing content.

mobile Ad hoc networks；publish/subscribe；content routing；location aware

TP393

A

1005-8788（2016）05-0075-04

10.13756/j.gtxyj.2016.05.022

2016-03-09

國家自然科學基金資助項目（61379159）；長江學者和創新團隊發展計劃基金資助項目（IRT1299）

任智（1971-），男，四川內江人。教授，博士，主要研究方向為寬帶無線移動通信網絡原理與技術。