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

任 智，張 勇，彭 晨，武 楊

（重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶 400065）

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

任 智，張 勇，彭 晨，武 楊

（重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶 400065）

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

移動自組織網(wǎng)絡(luò)；發(fā)布/訂閱；內(nèi)容路由；位置感知

0 引 言

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

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

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)模型

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

圖1 節(jié)點轉(zhuǎn)發(fā)區(qū)域

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

圖2 群組轉(zhuǎn)發(fā)區(qū)域

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

圖3 歐幾里德Steiner樹區(qū)域

1.2 問題描述

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

（1）位置速度信息需要通過Hello消息頻繁更新。而在節(jié)點沒有離開NFZ時，上次更新的信息依然可以將內(nèi)容轉(zhuǎn)發(fā)至此區(qū)域，并實現(xiàn)區(qū)域泛洪，使得節(jié)點收到此發(fā)布內(nèi)容。此時，更新導(dǎo)致冗余開銷。

（2）在訂閱節(jié)點回應(yīng)源節(jié)點的請求包（Join Request）時，回應(yīng)包（Join Reply）和之后一次的Hello包所起作用重復(fù)，產(chǎn)生冗余。

2 EPRLM

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

2.1 EPRLM新機制

2.1.1基于NFZ的信息更新機制

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

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

通過基于NFZ的信息更新，可以減少頻繁轉(zhuǎn)發(fā)至發(fā)布節(jié)點的信息更新Hello包，從而減少網(wǎng)絡(luò)的控制開銷，減緩網(wǎng)絡(luò)的通信負荷。

2.1.2 Join Reply包的捎帶機制

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

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

2.2 算法操作

EPRLM的主要操作步驟如下:

（1）發(fā)布節(jié)點周期性全網(wǎng)泛洪Join Request包（包含發(fā)布節(jié)點ID、位置及內(nèi)容摘要等信息）。

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

（3）節(jié)點收到Join Request包后，如不需要發(fā)布節(jié)點所擁有的內(nèi)容，則繼續(xù)廣播此消息。

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

3 仿真

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

表1 仿真默認參數(shù)

（1）消息傳送成功率

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

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

（2）消息端到端時延

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

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

（3）內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)

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

圖5 3種算法的內(nèi)容消息轉(zhuǎn)發(fā)次數(shù)比較

（4）控制包開銷

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

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

4 結(jié)束語

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

［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網(wǎng)絡(luò)仿真［M］.北京:清華大學(xué)出版社，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

國家自然科學(xué)基金資助項目（61379159）；長江學(xué)者和創(chuàng)新團隊發(fā)展計劃基金資助項目（IRT1299）

任智（1971-），男，四川內(nèi)江人。教授，博士，主要研究方向為寬帶無線移動通信網(wǎng)絡(luò)原理與技術(shù)。