無線傳感器網絡中數據查詢處理算法研究

摘要：提出一種改進的定向擴散路由，將傳感器網絡分簇，查詢興趣由sink節點發，只在各簇頭節點擴散，簇頭以廣播的方式在簇內發散興趣消息，簇成員將感知數據傳送到簇頭節點，簇頭負責將收到的數據進行融合后傳到sink節點。仿真結果表明，改進后的查詢路由比典型的查詢路由定向擴散具有更高的能量有效性和更低的時延，能較好地延長網絡的生命周期，提高了傳感器網絡數據查詢處理效率。

關鍵詞：查詢處理;無線傳感器網絡;定向擴散;查詢路由

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

文章編號：1001-3695(2008)05-1511-02

無線傳感器網絡是一種融合了傳感器技術、分布式計算技術、無線通信技術和數據庫處理技術的新一代網絡，能夠協作地實時監控、感知和采集各種環境和監測對象的信息，并對其進行處理，傳送到需要這些信息的用戶。傳感器網絡所獲得的感知數據集合類似于大型分布式數據庫，用戶可以通過對傳感器網絡所獲得的感知數據進行查詢和分析。然而，由于傳感器網絡節點的能量有限，計算能力有限、存儲能力有限、在傳感器網絡中進行數據查詢處理與傳統的數據庫有很大的區別，其中比較重要的一點就是為了延長傳感器網絡的生命周期，傳感器網絡中的數據查詢處理算法必須最小化能源消耗[1~3]。本文主要是從傳感器網絡數據查詢路由的角度來研究傳感器網絡中能量高效的數據查詢處理算法。

1查詢處理體系結構

圖1為傳感器網絡查詢處理體系結構的一個簡單示意圖。查詢任務由用戶通過sink節點（計算能力、存儲能力都比傳感器節點強很多，可以是一臺PC）對查詢語句進行解析和優化，并分發到傳感器網絡中的節點上，用戶也可以通過sink節點收集從傳感器網絡中傳送過來的感知數據，得到查詢結果；傳感器網絡中的節點根據一定路由協議和通信協議，收集感知數據并傳送到sink節點。為了延長傳感器網絡的生命周期，筆者將會采用基于定向擴散的分簇路由機制，并將查詢步驟分為三步進行：a）在基站上對查詢操作進行語法分析并進行優化處理；b）從sink節點將查詢注入網絡中或從網絡中收集數據；c）在節點處采樣數據并進行網內數據處理。

2查詢語言

傳感器網絡中查詢語言與標準的SQL語言類似[4]，其格式可以是SELECT－FROM－WHERE－ GROUP BY－HAVING模式，支持選擇、連接、映射、聚集及分組等操作。例如要讓每個傳感器節點每隔1 s報告一次自己的節點標志，以及感知到的亮度、溫度值，并持續10 s，可以這樣來寫查詢語句：SELECT nodeid， light， temp FROM sensors， SAMPLE PERIOD 1s for 10 s。在查詢中，所有傳感器數據被看成是一個單一的、虛擬的表，其中每個傳感器屬性占據一列。

3查詢路由

3．1定向擴散路由

傳感器網絡中能量高效的查詢路由對傳感器網絡的能量節省起著關鍵的作用，定向擴散[5]（directed diffusion，DD）是一種典型的基于查詢的路由協議[4]。該協議用屬性/值對命名數據。匯聚節點(sink)通過興趣消息發出查詢任務，采用洪泛方式傳播興趣消息到整個區域或部分區域內的所有傳感器。興趣消息用來表示查詢的任務，表達網絡用戶對監測區域內感興趣的信息，如監測區域內的溫度、濕度和光照等環境信息。在興趣消息的傳播過程中，協議逐跳地在每個傳感器節點上建立反向的從數據源到匯聚節點的數據傳輸梯度（gradient），傳感器節點將采集到的數據沿著梯度方向傳送到匯聚節點。使用查詢驅動機制按需建立路由，避免了保存全網信息，但是定向擴散路由在路由建立時需要一個興趣擴散的洪泛傳播，能量和時間開銷都比較大，尤其是當底層MAC協議采用休眠機制時可能造成興趣建立的不一致。圖2表示了DD協議的路由建立過程。

3．2改進的定向擴散路由

由于定向擴散路由在路由建立時需要一個興趣擴散的洪泛傳播，能量和時間開銷都比較大，尤其是當底層MAC協議采用休眠機制時可能造成興趣建立的不一致，提出一種改進的定向擴散查詢路由算法。該算法仿LEACH[6]分簇的思想，將傳感器網絡分簇，查詢興趣由sink節點發給各簇頭節點，興趣消息只在簇內洪泛，簇頭負責收集感知數據，并將收到的數據進行融合后傳到sink節點。圖3為傳感器網絡中分簇查詢處理。

3．2．1成簇算法

將傳感器網絡分為初始狀態（initial state）和分簇狀態（cluster state）兩種情形。將網絡中的節點分為簇成員節點（cluster member node）、簇頭節點（cluster header node）和候選簇頭節點（candidate cluster header node）。另外，假設所有的節點都可以與sink節點直接通信，sink節點知道所有節點的健康狀況。節點的健康狀況包括節點當前的剩余能量，傳感器部件、通信部件的工作情況等。在網絡初始狀態，所有的節點都處于平等地位，當有查詢任務時，sink節點發出一個分簇的消息（cluster formation message）。該消息中包含可以成為簇頭節點的能量閾值（threshold）。收到消息的節點根據自己當前的健康狀態來決定是否成為簇頭：若節點當前的剩余能量（residual energy）大于或等于能量閾值，則向自己一跳范圍內的鄰居節點宣布自己成為候選簇頭節點，若有兩個或兩個以上的鄰居節點都同時成為了候選簇頭節點；則當前剩余能量大者勝出，若當前剩余能量相等，則先聲明者勝出為簇頭節點，競選失敗的候選簇頭節點將自己變為簇成員節點。其他節點則根據自己到簇頭的跳數是否為一跳來選擇加入某個簇。若某個節點同時與幾個簇頭的距離均為一跳，則選擇先聲明的簇頭作為自己的簇頭。簇頭節點將自己的信息和簇成員的信息告知sink節點。

3．2．2興趣擴散

Sink節點得到成簇信息后，開始發散興趣消息。興趣消息包含任務類型、目標區域、數據發送速率、時間戳等參數。興趣消息由sink節點出發，只在簇頭節點間洪泛，每個簇頭節點在本地保存一個興趣列表。對于每一個興趣，列表中都有一個表項記錄發來該興趣消息的鄰居簇頭節點、數據發送速率和時間戳等任務相關信息，以建立該節點向sink節點傳遞數據的梯度。簇頭節點收到興趣消息后，以廣播的方式發給自己的簇成員節點。每個簇成員在本地保存一個興趣列表，列表中有一表項記錄發來該興趣消息的簇頭節點和時間戳等任務相關消息。若簇頭節點從鄰居簇頭節點收到的興趣消息與簇頭節點剛剛轉發的興趣消息一樣，則丟棄該信息；否則，轉發收到的興趣消息。簇成員節點也是如此。

3．2．3數據傳播

在簇內，當簇成員節點采集到與興趣匹配的數據時，簇成員將按簇頭制訂的TDMA時隙來向自己的簇頭發送感知數據；簇頭將收到的感知數據進行數據壓縮和數據聚集，然后將數據發送到梯度上鄰居簇頭節點，并按照梯度上的數據傳輸速率設定傳感器模塊采集數據的速率。一個簇頭節點可能從多個鄰居簇頭節點收到興趣消息，簇頭節點也可能向多個鄰居簇頭節點發送數據，sink節點可能收到經過多個路徑相同的數據。中間節點收到其他節點轉發的數據后，首先查詢興趣列表的表項，如果沒有匹配的興趣表項，就丟棄數據；如果存在相應的興趣表項，則檢查與這個興趣對應的數據緩沖池。數據緩沖池用來保存最近轉發的數據。如果在數據緩沖池中有與接收到的數據匹配的副本，說明已經轉發過這個數據，為避免出現傳輸環路而丟棄這個數據；否則，檢查該興趣表項中的鄰居簇頭節點信息。如果設置的鄰居簇頭節點數據發送速率大于等于接收的數據速率，則全部轉發接收的數據；如果記錄的鄰居節點數據發送速率小于接收的數據速率，則按照比例轉發。對于轉發的數據，數據緩沖池保留一個副本，并記錄轉發時間。

3．2．4路徑加強

與定向擴散一樣，在簇頭節點間通過正向加強機制來建立優化路徑，并根據網絡拓撲的變化修改數據轉發的梯度關系。興趣擴散階段是為了建立簇頭節點到sink節點的數據傳輸路徑，簇頭節點以較低的速率采集和發送數據，建立一個探測梯度。Sink節點在收到從簇頭節點發來的數據后，啟動建立到簇頭節點的加強路徑，后續數據將沿著加強路徑以較高的數據速率進行傳輸。

3．3查詢路由維護與更新

網絡一開始處于初始狀態，只有在有查詢任務時，才由sink節點發出分簇的控制消息，然后才開始分簇，這時網絡處于成簇狀態。這里假設分簇的時間是遠遠小于數據收集和查詢的。簇頭節點因為要對查詢消息進行洪泛，并對簇成員發來的數據進行數據壓縮和數據聚集，負責將簇內的信息發送到sink節點，其能量消耗比其他節點大很多，這樣就比較容易因能量耗盡而失效或剩余能量小于可以成為簇頭的能量閾值而不能再勝任簇頭。所以與文獻[6]一樣，讓節點輪流成為簇頭。在每輪查詢過程中，若某個簇頭的當前剩余能量接近能量閾值而成為臨界簇頭狀態，則向sink節點報告自己的能量狀態，sink節點根據臨界簇頭占總簇頭的比例來決定是否重新分簇。若需要重新分簇，則讓網絡進入初始狀態，并調用成簇算法進行分簇。每輪查詢結束后，也讓網絡進入初始狀態，當有下個查詢任務時，則調用成簇算法進行分簇。通過這樣的方式對查詢路由進行維護與更新。

4仿真與分析

為了驗證本文提出的查詢路由的能量高效，將改進后的定向擴散(improved directed diffusion，IDD）和典型的查詢路由定向擴散（directed diffusion，DD）在不同的網絡規模下的能耗和時延進行了比較，如圖4、5所示。仿真結果表明，改進后的查詢路由和定向擴散查詢路由隨著網絡中節點數量的增加其能量消耗和時延都有所增加，但改進后的查詢路由比典型的查詢路由定向擴散具有更高的能量有效性和更低的時延，能較好地延長網絡的生命周期。

5結束語

針對傳感器網絡中數據查詢處理不同于傳統數據庫中的數據查詢的特點，設計了一種傳感器網絡中數據查詢處理體系結構，并主要研究了傳感器網絡中數據查詢處理的查詢路由。定向擴散是傳感器網絡中典型的基于查詢路由，但定向擴散路由在路由建立時需要一個興趣擴散的洪泛傳播，能量和時間開銷都比較大。基于這一點，提出了一種改進的定向擴散查詢路由算法。仿真實驗表明，改進后的定向擴散查詢路由比起典型的定向擴散具有更小的傳輸時延和更小的能量消耗，能比較好地延長傳感器網絡的生命周期，提高傳感器數據查詢效率。



參考文獻：

［1］AKYILDIZ I F，SU Wei－lian，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8): 102－114.

[2]CUI L，JU H L，MIAO Y，et al.Overview of wireless sensor networks[J].Journal of Computer Research and Development，2005，42(1):163－174.

[3]LI Jian－zhong，LI Jin－bao，SHI Sheng－fei.Concepts，issues，and advance of sensor networks and data management of sensor network[J].Journal of Software，2003，14(10):1717－1727.

[4]JOHANNES G，SAMUEL M.Query processing in sensor networks[J].IEEE CS and IEEE Com Soc，2004，3（1）:46-55.

[5]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual ACM/IEEE Int’l Conf on Mobile Computing and Networking.Boston， MA:[s.n.]，2000:56-67.

[6]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy－efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences. Maui: IEEE Computer Society， 2000:3005-3014.

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