低開銷低延遲WSN多費馬點鏈多地域群播算法*

蘇 暢，臧李立，尙鳳軍，趙 曜

(1.重慶郵電大學計算機科學與技術學院，重慶400065;2.美國康奈爾大學計算機系，紐約州伊薩卡市，美國)

隨著無線傳感器網絡［1］技術的進一步發展，其應用領域越來越廣。傳感器節點的能量受限以及對數據實時性的高要求使得低能耗和低延遲成為無線傳感器網絡通信協議的重要衡量指標。基于地理位置的路由協議因其對網絡拓撲結構信息的極低需求使其算法簡單高效而且開銷小，其路由發現和數據傳輸過程依靠節點自身及其鄰節點的位置信息(通過 GPS 等定位設備［2－6］獲取)。

無線傳感器網絡極強的應用相關性使基于地理位置路由的地域群播(Geocasting:即源節點向WSN中特定地理位置區域內的所有節點發送信息)應運而生。其應用廣泛，如:森林管理中心需要向森林中高火險區域內所有節點發送命令，使區域內節點及時監測并匯報其周圍溫度狀況;交通控制中指揮中心要向交通擁擠地區所有節點及時發出控制命令。

地域群播通過兩個過程完成傳輸:源節點與目標區域的通信及目標區域內信息的傳輸。網絡拓撲的不規則性，尤其是路由空洞的存在，使信息如何低能耗、高可靠性、低延遲地傳輸到目標區域成為目前研究的熱點。Brad Karp等提出的GPSR算法［7］，以貪心算法為基礎，結合面路由的方法，成功解決了貪心算法因遇到路由空洞而導致算法失敗的問題;胥楚貴等提出的最佳匹配節點策略［8］通過選取距離由空洞邊界所圍成多邊形的最小覆蓋圓圓心最近的非活躍節點來替換失敗節點的方式修復覆蓋空洞;F.Yu 提出的彈性路由(Elastic Routing)算法［9］通過路由路徑的反方向更新Sink節點的位置信息，大大降低了能量開銷和傳輸延遲;針對密集型網絡的目標區域內信息的傳輸多采用簡單泛洪的方式，如ALURP［10］、LBM［11］等算法。而實際中網絡的密度狀況是不可知的，稀疏網絡嚴重降低了網絡的連通度［12］，簡單泛洪無法保證區域內所有節點收到信息，因此 Karim Seada等提出了 GFPG［13］算法。

多目標區域地域群播的目標區域數量以及位置均未知，這種復雜性注定了單目標區域算法無法滿足其需求。多路徑單地域群播算法［14］中源節點依次將信息傳輸到每個目標區域內，能量開銷極大;簡單目標區域鏈算法［14］通過鏈接所有目標區域減少了源節點的能量開銷，但整個網絡的能量開銷依然很大;Lee Sung-Hee等提出的單費馬點鏈算法［12］將所有目標區域與源節點連接到一條費馬點鏈上，如圖1(a)所示，雖然可以降低整個網絡的能量消耗，但是其健壯性和網絡傳輸延遲存在著缺陷。

圖1 多地域群播算法

本文提出一種基于多費馬點鏈低能耗低延遲多地域群播算法，在保持較低能量消耗的基礎上，降低了傳輸延遲，并在NS2環境下對LLA算法和現有的算法進行仿真分析。

1 多費馬點鏈算法

多費馬點鏈算法包括兩部分:第1是基于源節點傳輸區域的網格劃分以及網格中簇頭的選擇，第2是通過引入四邊形費馬點解決建立三角形費馬點失敗的問題，如圖1(b)所示。

1.1 網格劃分及簇頭選擇

假設數據源節點A的位置坐標為(x0，y0)，則以該節點為中心建立如下坐標系:以直線y=y0為該坐標系的x軸，以直線x=x0為該坐標系的y軸。此坐標系將網絡分成四網格。當多數目標區域集中于某一網格中時，按如下規則劃分:假設網絡中目標區域數量為n，網格劃分的層次為N

直到經過N次劃分的網格中的目標區域的數量小于等于n/2N或網格中的目標區域數量均≤4。

網格中選取距離源節點最近的目標區域的中心點作為該網格的簇頭，不同源節點對于不同的目標區域產生不同的簇頭節點，避免了固定或單一簇頭導致其消耗能量過快而死亡。

下面對基于源節點傳輸區域的網格劃分及網格中選取距離源節點最近的目標區域作為簇頭的方法進行性能分析。

假設有n個目標區域，費馬點之間的平均傳輸延遲為t，費馬點到其相鄰節點之間的傳輸延遲平均為 T，則:

?delay(n)=nt+T，(delay(n)為第n個節點接收到數據包時的延遲時間)(avg(delay(n))為n個目標區域接收到數據包時的平均延遲時間)。分成網格后，每個網格有n/4個目標區域，由于數據在網格內同時通信，其平均延遲可以認為等同于單一網格的延遲，考慮上面的假設，則:

通過以上分析在傳輸延遲方面該方法優于單費馬點鏈算法。源節點將信息傳送到簇頭節點后，由簇頭節點通過費馬點鏈轉發到相應的目標區域內。

1.2 網格費馬點鏈

網絡中目標區域需要向其感興趣的節點發送位置信息及數據收集請求，源節點則需要記錄向其發送請求的所有目標區域的位置信息以便計算費馬點鏈。

三角形中一定存在費馬點，如圖2所示，尋找△ABC費馬點的過程如下。

圖2 三角形費馬點

在△APC中，將∠PAC按逆時針方向旋轉60°，點P和點C分別落于點P1和C'，的最小值即的最小值，即C'到點B的直線距離

這時點P和P1都在線段C'B上，同理我們可得點P必在線段B'A和線段A'C上，三條線段的交點即是三角形的費馬點。因此只需找到A'、B'和C'中的任意兩點就可以找到該三角形的費馬點，如圖2所示。

單費馬點鏈算法存在著明顯的缺陷:局部能量開銷大、極大的傳輸延遲、可靠性差。當費馬點存在于三角形外部時(即三角形任意一內角大于等于120°)，按照順序往下繼續尋找目標區域，然后以這三個目標區域和簇頭組成的四邊形為基礎，尋找四邊形的費馬點，找到該費馬點后，繼續尋找接下來的三角形的費馬點，直到所有的目標區域都連接到費馬點鏈上。如圖3所示，有兩種情況:凸四邊形(如圖3(a)所示)和凹四邊形(如圖3(b)所示)。兩種情況下∠ABC＞120°，因此選取第四個目標區域D形成四邊形，計算出四邊形的費馬點后再以該費馬點、簇頭A和下一個目標區域的中心點E形成的三角形繼續尋找費馬點。

圖3 四邊形費馬點鏈

定理1 凸四邊形費馬點的位置為對角線的交點。

證明:假設凸?ABCD中，對角線AC、BD交于點P，如圖4所示。

圖4 四邊形費馬點

定理2 內含三角形中內三角形的兩邊之和小于外三角形的兩邊之和。

定理3 凹四邊形的費馬點在凹點上，即四邊形內角大于180°的頂點上。

證明:如圖5(b)和5(c)兩種情況所示:F點均為四邊形內部異于凹點的任意一點，在圖5(b)中，△CDB是△CFB的內含三角形，由定理2可知:

在圖5(c)中，△ADB是△AFB的內含三角形，

由上證明可得出結論:凹四邊形的費馬點在其凹點上。

圖5 四邊形費馬點

通過引入四邊形費馬點保證了所建費馬點鏈的連續性，然后源節點將信息沿著費馬點鏈傳送到所有的目標區域，到達目標區域的信息在該區域內泛洪，完成地域群播路由過程。該方法能夠減少單個網格內節點的能量消耗，降低整個網絡的能量開銷。

2 仿真結果與分析

2.1 仿真環境

我們使用的仿真工具是NS2.30，MAC層采用的是802.11協議。我們構建了如下的無線傳感器網絡:400個無線傳感器節點隨機地分布在2 000 m×2 000 m的正方形區域內，地域群播區域為半徑250 m的圓形區域。整個仿真過程中，對每種算法我們分別設定并隨機選取網絡中的地域群播區域的數量為2、4、6、8、10、12、14、16 個。

仿真中我們采用三個指標來衡量該算法的性能:包的成功傳輸比率、端到端的平均延遲和數據傳輸到目標區域內這一過程中的平均能量消耗(下文簡稱為平均傳輸能量消耗)。包的成功傳輸比率定義為網絡中所有的目標節點成功接受到數據包的總量與網絡中所有數據源節點發送的數據包的總量的比值;端到端的平均延遲定義為網絡中所有數據包的延遲的總和與網絡中所有數據包總量的比值;平均傳輸能量消耗定義為網絡中所有傳輸的數據包的總字節數與網絡中產生的數據包的總量和數據包成功傳輸比率的乘積的比值。

2.2 仿真結果和分析

圖6展示了數據包的成功傳輸比率。從圖中可以看出單費馬點鏈算法、多路徑單地域群播算法和本文中提出的多費馬點鏈算法的數據包的成功傳輸比率在95.5% ～97%之間波動，多路徑單地域群播算法采用的是每次只向一個區域發送數據，而基于費馬點鏈的兩種算法的第1階段都是采用GPSR算法，可以很好的解決導致成功傳輸比率下降的主要因素——路由空洞，并且對鏈路進行了優化。當目標區域數量大于6個的時候，簡單目標區域鏈算法的成功傳輸比率呈現線性下降趨勢，當區域數量為12時，成功傳輸比率已降到95%，數量為16時降到93.5%，因為簡單目標區域鏈算法存在兩個方面的缺陷:無法解決路由空洞并且路由路徑最長。通過以上分析，多費馬點鏈算法可以有效地保證將數據傳輸到目標區域，其數據成功傳輸比率高且穩定。

圖6 數據包成功傳輸比率

圖7 端到端的平均延遲

圖7展示了端到端的平均延遲。簡單區域鏈算法的延遲明顯高于其它3種算法，當區域數量為16時，平均延遲為150 ms，是其它3種算法的300% ～500%;而單費馬點鏈算法的平均延遲高于多費馬點鏈算法，目標區域從4變化到16時，其延遲是多費馬點鏈算法的200%，因為該算法單一的傳輸鏈路導致其傳輸路徑過長;目標區域大于10的時候，多路徑單地域群播算法的延遲比多費馬點鏈算法高出30% ～40%，因為其延遲主要由兩部分組成:數據傳到第1個和最后1個目標區域的時間和事件在隊列中的等候時間，而多費馬點鏈算法是在4個網格同時通信，因此目標區域數量對其的影響僅為其它算法的1/4。通過以上分析，多費馬點鏈算法在平均延遲上要明顯好于其它3種算法。

圖8展示了網絡中的平均傳輸開銷。當區域數量為4的時候，4種算法的平均開銷基本相同，為7 kbit;區域數量大于6時，簡單區域鏈算法和多路徑單地域群播算法的開銷，明顯高于基于費馬點鏈的算法，目標區域數量從10開始一直到16，其開銷比其它基于費馬點鏈的算法平均高出20%～30%。因為基于費馬點鏈的兩種算法對傳輸鏈路進行了優化，鏈路數要比以上兩種算法少。通過以上分析，單費馬點鏈算法和多費馬點鏈算法在平均傳輸開銷上明顯低于簡單區域鏈算法和多路徑單地域群播算法。

圖8 平均傳輸開銷

3 結束語

多地域群播的目標區域數量和位置均未知，這種復雜性導致目前無線傳感器網絡多地域群播算法都無法做到能量和傳輸延遲的平衡。本文提出了一種新的基于多目標區域的多費馬點鏈算法，主要思想是以源節點為中心將自身傳輸區域分為4個網格，網格中選取距離源節點最近的目標區域的中心點為簇頭，并以該簇頭與目標區域形成三角形與四邊形相結合的費馬點鏈。通過仿真實驗表明多費馬點鏈算法在保持較低能量消耗的同時大大降低了傳輸延遲。

［1］ Akyildiz I F，Su W L，Sankarasubramaniam Y.A Survey on Sensor Networks［J］.Communications Magazine，2002，40(8):102－114.

［2］ Li J Y，JAnnotti J，Couto D，et al.A Scalable Location Service for Geographic Ad Hoc Routing［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，New York，2000:120－130.

［3］ Xue Y，LI B C，Nahrstedt K.A Scalable Location Management Scheme in Mobile Ad-Hoc Networks［C］//Proc.LCN 2001.26th Annual IEEE Conference，Tampa，2001:102－111.

［4］ He T，Huang C，Blum B，et al.Rangefree Localization Schemes for Large Scale Sensor Networks［C］//Proc.of the 9th Annual International Conference on Mobile Computing and Networking，2003:81－95.

［5］ Seada K，Helmy A.Rendezvous Regions:A Scalable Architecture for Service Location and Data-Centric Storage in Large-Scale Wireless Networks［C］//Parallel and Distributed Processing Symposium，Proc.18th International，2004:218－225.

［6］ Stojmenovic I，Liu D D，Jia X H.A Scalable Quorum-Based Location Service in Ad Hoc and Sensor Networks［C］//Mobile Adhoc and Sensor Systems，Vancouver，2006:489－492.

［7］ Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless Networks［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，Boston，2000:243－254.

［8］ 胥楚貴，鄧曉衡，鄒豪杰.無線傳感器網絡覆蓋空洞修復策略［J］.傳感技術學報，2010，23(2):256－259.

［9］ Yu F，Park S，Lee E，et al.Elastic Routing:A Novel Geographic Routing for Mobile Sinks in Wireless Sensor Networks［C］//IET The Institution of Engineering and Technology，2010，4(6):716－727.

［10］ Wang G，Wang T，Jia W，et al:Adaptive Location Updates for Mobile Sinks in Wireless Sensor Networks［J］.The Journal of supercomputing，2009，47(2):127－145.

［11］ Ko Y B，Vaidya N H.Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks［J］.Mobile Networks and Applications，2002，7(6):471－480.

［12］ Seada K，Helmy A.Efficient Geocasting with Perfect Delivery in Wireless Networks［C］//Proceedings of IEEE WCNC 2004，Atlanta，2004，4:2551－2556.

［13］張強，孫雨耕，劉麗萍.邊界節點對無線傳感器網絡連通性的影響［J］.傳感技術學報，2011，24(5):737－741.

［14］ Lee S H，Ko Y B.Efficient Geocasting with Multi-Target Regions in Mobile Multi-Hop Wireless Networks［C］//Wireless Networks.2010，16(5):1253－1262.