大規模無線傳感器網絡查詢方法——ＣＢＱＭ

摘要：提出一種適用于大規模、高查詢率而單次查詢需要傳輸的數據量很小、位置信息無關的無線傳感器網絡查詢方法——CBQM。該方法以小世界理論為依據，在CARD和TRANSFER協議的基礎上，引入了方向邊節點，改進了contact的選擇方法，降低了協議的能耗，提高了網絡生命周期。通過仿真得出，在保證查詢成功率的前提下，CBQM的查詢最優能耗與CARD相比降低了約38%，比TRANSFER降低了40%以上。

關鍵詞：路由協議；小世界；長程連接；無線傳感器網絡

中圖分類號：TP393．02文獻標志碼：A

文章編號：1001-3695(2007)12-0333-03

查詢方法在無線傳感器網絡中具有非常重要的作用，同時也是非常具有挑戰性的問題。許多重要的無線傳感器網絡路由協議是基于查詢的，如directed diffusion、TRANSFER和rumor等。本文提出了一種基于小世界理論^[1~3]的無線傳感器網絡查詢方法——CBQM。該方法適用于大規模、位置信息無關、高查詢率而單次查詢需要傳輸的數據量很小的無線傳感器網絡。CBQM方法著眼于降低路由建立的能量消耗，尋找可行的路徑，而不是最優路徑。由此降低單次查詢的總能耗，進而提高網絡的生命周期。

1相關工作

小世界理論表明，在規則網絡中隨機加入少量的長程連接（shortcuts），將大大地降低網絡直徑。基于該理論，許多研究人員在無線傳感器網絡中引入長程連接，以改善網絡的查詢性能。例如：Sharma在網絡中引入了有線長程連接^[4]。2002年，美國加州大學洛杉磯分校的Ahmed Helmy教授提出Ad hoc網絡的各個節點不僅維護鄰居節點的狀態，而且還選擇維護少數較遠節點的狀態，這些較遠的節點叫做contact^[5]。Contact就是網絡中的長程連接，它使得網絡成為一個小世界，大大降低了查詢源與目標的分離度。隨后，針對不同的contact選擇方法，又設計出了CARD^[6，7]、MARQ^[8]和TRANSFER^[9]協議。MARQ主要是針對移動性較強的Ad hoc網絡，這里不作探討。CARD采用邊方法（EM）或概率方法（PM）來預先選擇contact^[6]，而后通過周期性發送validate的方式維護contact；而TRANSFER協議則采用動態的方式創建contact。當查詢開始后，查詢信息到達某個節點時，由該節點判斷，如果必要，才開始創建contact^[9]。CARD架構增加了contact的維護開銷；TRANSFER協議不需要維護contact，它在開始查詢后才按需創建contact，因此增加了查詢延遲，同時也增加了多次創建contact而帶來的能耗。

本文提出的CBQM將在CARD和TRANSFER的基礎上，改進contact創建方法，目的是降低協議的查詢能耗。

2CBQM查詢方法

CBQM查詢方法主要包括鄰居維護、contact選擇與維護、查詢三個環節。

2．1相關定義

文中的相關定義基本沿用文獻[6]中的相關定義，如圖1所示。

1）節點的鄰居位于該節點周圍R跳以內的所有節點，其中R≥1是正整數，一般取值不會太大；恰好位于該節點周圍R跳上的鄰居，叫做邊節點E。

2）Contact距離rContact距離源節點的限制跳數，為了避免重疊，令r≥2R。

3）最大contact數量NoC每個節點可以選擇contact的最大數量。

4）搜索深度D源節點查詢contact的級數（contact的contact）。

2．2創建并維護鄰居和contact狀態

圖5比較了CBQM和CARD在鄰居建立和contact建立階段的數據包流量曲線，間接反映了能耗（數據包流量越大，網絡能耗越大）。實驗網絡節點數是200。如圖5所示，在30 s之前，CBQM和CARD都出現了流量峰值，這是由于在鄰居建立是采用泛洪的方法，造成了大量的數據包流量；30 s之后是contact建立階段，該階段CBQM較CARD節省50%左右的能耗。

圖6顯示在不同規模的網絡中，CBQM單次查詢的平均能耗相比CARD、TRANSFER和flood都優越，并且隨著網絡規模的擴大，CBQM的性能體現得更加明顯。實驗表明，在保證查詢成功率的前提下，CBQM的單次查詢平均最優能耗比CARD低38%左右（5 000節點時），而比TRANSFER低40%以上。

4結束語

本文提出了一種無線傳感器網絡查詢、資源發現方法—CBQM。它在CARD架構的基礎上，改進了contact的選擇方法。通過仿真實驗表明，CBQM在能耗方面具有非常優越的表現。

參考文獻：

[1]WATTS D J，STROGATZ S H.Collective dynamics of small－world networks[J].Nature，1998，393(6)：440-442.

[2]NEWMAN M E J，WATTS D J.Scaling and percolation in the small－world network model[J].Phys Rev E，1999，60(2):7332-7342.

[3]NEWMAN M E J. Models of the small world[J]. J Stat Phys，2000，101:819-841.

[4]SHARMAG，MAZUMDAR R.Hybrid sensor networks: a small world[C]//Proc of the 6th ACM International Symposium on Mobile Ad hoc Networking and Computing. 2005:366-377.

[5]HELMY A.Architectural framework for large－scale multicast in mobile Ad hoc networks[C]//IEEE International Conference on Communications(ICC 2002). 2002:2036-2042.

[6]HELMY A，GARG S，PAMU P，et al.Contact based architecture for resource discovery (CARD) in large scale MANETS[C]//IEEE ACM IPDPS Int’l Workshop on Wireless， Mobile and Ad hoc Networks(WMAN). 2003:219-227.

[7]HELMY A，GARG S，PAMU P，et al.CARD: a contact－based architecture for resource discovery in Ad hoc networks[J].MONET Journal，2005，10:99－113.

[8]HELMY A.Mobility－assisted resolution of queries in large－scale mobile sensor networks (MARQ)[J]. Computer Networks Journal: Elsevier Science， 2003，43(4):437-458.

[9]HELMY A.TRANSFER: transactions routing for Ad hoc networks with efficient energy[C]//Proc of IEEE GLOBECOM. 2003:398-404.

[10]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D，et al.Directed diffusion for wireless sensor networking[J].IEEE/ACM Trans on Networking，2003，11(1):2－16.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”