低佔空比無線傳感器網絡中最小時延的數據收集方法
2024-01-25 13:11:15
專利名稱：低佔空比無線傳感器網絡中最小時延的數據收集方法
技術領域：
本發明涉及無線傳感器網絡技術領域，尤其涉及一種低佔空比無線傳感器網絡中最小時延的數據收集方法。
背景技術：
近年來，通信技術、嵌入式技術和傳感器技術的飛速發展使無線傳感器網絡的大規模應用成為可能。無線傳感器網絡能夠拓展人們的信息獲取能力，極大地方便人們的信息交流，因此具有十分廣闊的應用前景，能應用於軍事國防、工農業控制、城市管理、生物醫療、環境監測、搶險救災等諸多領域。無線傳感器網絡是由部署在監測區域內大量能量有限的微型傳感器節點(簡稱節點)組成，通過無線通信方式形成一個多跳的自組織網絡，其目的是協作地感知、採集和處理網絡覆蓋區域中感知對象的信息，並發送給處理中心(sink節點)即匯聚節點。由於傳感器節點攜帶的電池能量有限，再加上節點個數多，分布區域廣，有些甚至部署在危險區域，因此傳感器節點通過更換電池的方式來補充能量是不現實的。如何設計出節能高效的網絡協議來最大化網絡壽命是無線傳感器網絡面臨的首要挑戰。睡眠喚醒機制是一種提高網絡壽命的有效方法。傳感器節點通常有兩種低佔空比的狀態喚醒狀態和睡眠狀態。在喚醒狀態下，傳感器節點能夠感知周圍物理世界信息，並發送和接收相關信息，而在睡眠狀態下，傳感器節點將關閉所有通信和感知模塊，只開啟時鐘功能。低佔空比睡眠喚醒機制主要是採用周期性的喚醒節點的方式，以減少不必要的數據轉發和接收，讓傳感器節點儘可能多的時間處於睡眠狀態，而不至於影響網絡的正常通信和功能。由於只有通信雙方都處於喚醒狀態的時候才能進行正常通信，一旦有一方處於睡眠狀態，則另一方需要等待到下一個周期對方喚醒時才能進行數據傳輸，這就帶來了「睡眠時延」。在低佔空比網絡中，即節點的喚醒時間與睡眠時間之比很小的時候，端到端數據傳輸時延將極度惡化，導致網絡數據時效性大大降低。在突發事件監測的無線傳感器網絡中，對數據收集的實時性要求很高，一旦傳感器節點監測到異常的狀況，要保證能以最快的速度將信息發送到處理中心。因此如何在提高能效的低佔空比無線傳感器網絡中設計出時延最優的數據收集方法是一個很值得研究的問題。由於傳感器節點被周期性喚醒，因此網絡的邏輯拓撲隨時間處於動態變化中，如何在動態拓撲中設計一種能夠達到時延最小的數據收集方法具有很大的挑戰。普林斯頓和南加州大學的學者共同提出了一種時延最優的數據收集方法，並結合了信道分配和功率控制機制，該方法給出了在單信道和多信道兩種情況下時延最小的鏈路調度方法，但是該方法沒有考慮傳感器節點的「睡眠時延」，所使用的網絡模型中假設節點一直處於喚醒狀態，並且只能在樹狀拓撲下才能實現該時延最優調度方法。史丹福大學的學者提出了一種基於時分多址接入(Time Division Multiple Access, TDMA)的無線傳感網絡中權衡能耗和 時延的數據收集方法。該方法是在給定時隙長度的前提下，能夠找到一種時延最小的鏈路調度策略，但是該方法也沒有考慮傳感器節點的周期性睡眠機制，即也沒有考慮到「睡眠時延」對數據收集時延帶來的影響。
發明內容
針對上述技術問題，本發明的目的在於提供一種低佔空比無線傳感器網絡中最小時延的數據收集方法，其解決了由於睡眠喚醒機制帶來的「睡眠時延」過長和數據收集時效性下降的問題，能在保證網絡能效性的前提下，找到一種數據收集的路由和鏈路調度聯合策略，並能夠有效避免由於數據碰撞重傳帶來的時延問題。為達此目的，本發明採用以下技術方案—種低佔空比無線傳感器網絡中最小時延的數據收集方法，包括如下步驟
A、根據實際網絡的物理拓撲G和各節點的喚醒周期π，將動態變化的邏輯拓撲轉化成靜態的、在時間上延拓的虛擬網格網絡；B、基於虛擬網格網絡，將初始虛擬網格網絡拓展時間Λ設為節點Ili產生的數據包到達sink節點所需的最小時間中的最大值max丨LfKJ，其中，η為網絡中的總節點數；C、在虛擬網格網絡中尋找從超級源節點s到超級sink節點d之間滿足無衝突要求的最大流；D、判斷所述最大流是否等於源節點個數；若判斷結果為否，則將虛擬網格網絡在時間上繼續延拓，直到在找出的滿足無衝突要求的最大流等於源節點個數為止。特別地，所述步驟A還包括根據節點所承擔任務的不同，將節點分為三種葉子節點、中間節點和sink節點，其中，所述葉子節點只作為源節點發送數據包，所述中間節點既作為源節點發送數據包，又接收和轉發來自鄰居節點的數據包，所述Sink節點只作為目的節點接收數據包。特別地，所述步驟A具體包括Al、對於實際網絡的物理拓撲G中的每個節點Iii,在T時間內的任意時刻t，處於喚醒狀態的節點映射到虛擬網格網絡中在時間上延拓的虛擬喚醒節點Ni;t ；A2、在虛擬網格網絡中增加一個超級源節點s和超級sink節點d ；A3、當實際網絡的物理拓撲G中節點Iii是葉子節點，並且到節點η」存在有向邊時，如果節點Iii第一次t時刻喚醒，節點η」在時間t之後的P時刻喚醒，則在虛擬網格網絡中增加從\t到Ν」，ρ的有向邊；A4、當實際網絡的物理拓撲G中節點Iii是中間節點，並且到節點η」存在有向邊時，如果節點Iii和η」的喚醒時間分別是t和P，並且t和P都在T時間內，p>t，則在虛擬網格網絡中增加從\t到Ν」，ρ的有向邊；A5、當實際網絡的物理拓撲G中節點Iii是sink節點時，則在虛擬網格網絡中建立其對應的所有虛擬喚醒節點到超級sink節點d之間的有向邊；A6、在虛擬網格網絡中建立從超級源節點s到所有源節點對應的第一個虛擬喚醒節點的有向邊。特別地，所述步驟B中節點Iii產生的數據包到達sink節點所需的最小時間!^。通過Dijkstra算法獲得。特別地,所述步驟C包括通過Ford-Fulkerson最大流算法找到使數據收集時延最小的數據包傳輸路徑。本發明將將動態變化的邏輯拓撲轉化成靜態的、在時間上延拓的虛擬網格網絡，大大降低了數據收集算法的複雜度，而且採用無競爭的TDMA媒體接入機制，找到時延最小的數據收集路徑，並保證在數據收集過程不會發生數據衝突。在低佔空比無線傳感器網絡中，本發明提高了數據收集的時效性，並保證了整個網絡的能效性，並且節點只在喚醒狀態進行數據接收，其它時間都進入睡眠狀態，使網絡壽命最大化。
圖1為本發明實施例提供的低佔空比無線傳感器網絡中最小時延的數據收集方法流程圖；圖2a為本發明實施例提供的無線傳感器網絡無衝突的限制條件一示意圖；圖2b為本發明實施例提供的無線傳感器網絡無衝突的限制條件二示意圖； 圖3為本發明實施例提供的實際網絡的物理拓撲G和節點喚醒周期示意圖；圖4為本發明實施例提供的虛擬網格網絡示意圖；圖5為本發明實施例提供的虛擬網格網絡的最大流示意圖；圖6為本發明實施例提供的MDCD算法流程圖。
具體實施例方式為使本發明的目的、技術方案和優點更加清楚，下面結合附圖和實施例對本發明作進一步說明。請參照圖1所示，圖1為本發明實施例提供的低佔空比無線傳感器網絡中最小時延的數據收集方法流程圖。針對低佔空比無線傳感器網絡的應用特點，本發明建立了如下的網絡模型在低佔空比無線傳感器網絡中，節點具有兩種狀態喚醒狀態和睡眠狀態。節點在喚醒狀態下可以感知周圍物理世界，並接收從鄰居節點發來的數據包。為了讓數據包能夠更加快速地傳輸，節點可以在任何狀態下進行數據包的發送，只要下一跳節點處於喚醒狀態。在每個時隙中，每個節點只能發送一個數據包，並且網絡中除了 sink節點，其它節點都會在初始時刻產生一個數據包。數據收集時延是指所有源節點產生的數據包都到達sink節點所用的時間。在TDMA媒體接入協議中，將時間分為很多相同的時隙，如果該時隙節點處於喚醒狀態，則用「I」表示，如果處於睡眠狀態，則用「O」表示。節點喚醒周期用表示。如果節點給定的工作機制是「 η =0100」，表明在第一個工作周期π內，節點在第二個時隙被喚醒，其它時隙都處於睡眠狀態。本實施例中低佔空比無線傳感器網絡中最小時延的數據收集方法包括如下步驟步驟S101、根據實際網絡的物理拓撲G和各節點的喚醒周期π，將動態變化的邏輯拓撲轉化成靜態的、在時間上延拓的虛擬網格網絡。根據節點所承擔任務的不同，將節點分為三種葉子節點、中間節點和sink節點，其中，所述葉子節點只作為源節點發送數據包，所述中間節點既作為源節點發送數據包，又接收和轉發來自鄰居節點的數據包，所述sink節點只作為目的節點接收數據包。本實施例中將實際網絡的物理拓撲G映射到虛擬網格網絡(Virtual GridNetwork, VGN)的具體過程如下步驟S1011、對於實際網絡的物理拓撲G中的每個節點ni;在T時間內的任意時刻t，處於喚醒狀態的節點映射到虛擬網格網絡中在時間上延拓的虛擬喚醒節點Ni, t。步驟S1012、在虛擬網格網絡中增加一個超級源節點s和超級sink節點d。步驟S1013、當實際網絡的物理拓撲G中節點Iii是葉子節點，並且到節點η」存在有向邊時，如果節點Ili第一次t時刻喚醒，節點Ilj在時間t之後的P時刻喚醒，則在虛擬網格網絡中增加從Ni t到Nj p的有向邊。由於葉子節點之可能在第一次喚醒時刻有數據包需要發送，所以不需要考慮其它 喚醒時候到其它節點的邊。步驟S1014、當實際網絡的物理拓撲G中節點Iii是中間節點，並且到節點η」存在有向邊時，如果節點Ili和Ilj的喚醒時間分別是t和P，並且t和P都在T時間內，p>t，則在虛擬網格網絡中增加從Ni, t到Nj，p的有向邊。步驟S1015、當實際網絡的物理拓撲G中節點Iii是sink節點時，則在虛擬網格網絡中建立其對應的所有虛擬喚醒節點到超級sink節點d之間的有向邊。步驟S1016、在虛擬網格網絡中建立從超級源節點s到所有源節點對應的第一個虛擬喚醒節點的有向邊。步驟S102、基於虛擬網格網絡，將初始虛擬網格網絡拓展時間Λ設為節點Iii產生的數據包到達sink節點所需的最小時間2^中的最大值max=1 ，其中，η為網絡中的總節點數。本實施例中節點Iii產生的數據包到達sink節點所需的最小時間/ 通過Dijkstra算法獲得。Dijkstra算是一種已知的最短路徑算法，其根據整個網絡拓和各鏈路的長度，可以求得最短路徑，在此不再詳細說明。步驟S103、在虛擬網格網絡中尋找從超級源節點s到超級sink節點d之間滿足無衝突要求的最大流。通過最小時延的數據收集路徑算法(Minimum Data CollectionDelayalgorithm,MDCD)在虛擬網格網絡中尋找從超級源節點s到超級sink節點d之間滿足無衝突要求的最大流。MD⑶算法通過Ford-Fulkerson最大流算法找到使數據收集時延最小的數據包傳輸路徑，並保證在整個數據收集過程中通過該算法找出的收集路徑不會發生數據衝突。Ford-Fulkerson最大流算法一種比較容易實現的網絡最大流算法,應用較為廣泛，在此不再詳細說明。下面針對所述數據衝突問題進行說明。為了保證數據傳輸過程中不發生衝突，需要考慮節點的半雙工特性，即節點不能同時進行接收和發送數據包。如圖2a和圖2b所示，這兩種情況在鏈路調度過程中是不允許出現的，一旦出現將會發生數據衝突。如圖2a所示，節點j在接收節點i發送的數據時，節點j不能發送數據給節點m。如圖2b所示，節點2和節點3不能同時給節點I發送數據。因此在考慮尋找虛擬網格網絡中的最大流時應該將以上兩種衝突情況排除在外。步驟S104、判斷所述最大流是否等於源節點個數；若判斷結果為否，則將虛擬網格網絡在時間上繼續延拓，直到在找出的滿足無衝突要求的最大流等於源節點個數為止。如圖3所示，圖3為本發明實施例提供的實際網絡的物理拓撲G和節點喚醒周期示意圖。以圖3所示的實際網絡的物理拓撲G為例對本發明的實現過程進行具體的說明。本實施例中實際網絡的物理拓撲G映射到虛擬網格網絡的具體過程如下1、如圖3所示，節點I的喚醒周期是「1000」，假定數據收集的持續時間是11個時隙，那麼節點I會在第1、5、9三個時隙被喚醒，因此節點I對應虛擬網格網絡中的虛擬喚醒節點為N1,1; \5和N1,9。節點2、節點3和節點4轉換成虛擬網格網絡中的虛擬喚醒節點同理可得。2、如圖3所示，葉子節點I在其鄰居節點3喚醒的時候可以將數據包發送給節點3，因此可以在虛擬網格網絡中添加有向邊Ν1Λ — N3j2, N1j1 — N3j6和Nm — Ν3,1(ι，如圖4所示。同理可得對於葉子節點2，同樣也是在其鄰居節點3處於喚醒狀態時可以將數據包發送給節點3，因此可以在虛擬網格網絡中添加有向邊Ν2，4 — N3j6和Ν2，4 — N3aoo 3、如圖3所示，中間節點3作為源節點，其可在鄰居節點4處於喚醒狀態時發送數據包給節點4，因此可以在虛擬網格網絡中添加有向邊Ν3，2 — N4j3, N3j2 — N4j7和Ν3，2 — N4,no節點3作為中繼節點，可以在其處於喚醒狀態時接收數據包，並轉發給鄰居節點4。因此可以在虛擬網格網絡中添加有向邊N3，6 — N4j7, N3j6 — N4jll和N3atl — N4jllo4、如圖4所示,節點4作為sink節點，可以在虛擬網格網絡中添加超級sink節點d對應的虛擬喚醒節點到超級sink節點d之間的有向邊，因此可以添加有向邊N43 — d，N4,7 — d和N4ai — d,如圖3所不。5、如圖4所示，建立超級源節點s到各源節點第一個喚醒周期內對應的虛擬喚醒節點的有向邊，因此可以在VGN中添加有向邊s — Nia, s — N2j4和s — N3j20在執行完上述步驟I至5之後，如圖3所示的實際網絡的物理拓撲G和節點喚醒周期就轉換成靜態的虛擬網格網絡，具體情況，如圖4所示。基於虛擬網格網絡採用MDCD算法來找到符合無線傳感器網絡中無衝突限制的最小時延數據收集路徑。在如圖4所示的虛擬網格網絡中，尋找從超級源節點s到超級sink節點d的最大流，求得在虛擬網格網絡中使最大流等於源節點個數的最小時間拓展。所得到的結果如圖5所示，最小時延拓展為11個時隙時，從超級源節點s到超級sink節點d的最大流剛好等於源節點個數3。最大流的流向即為數據收集的路徑節點3在第3個時隙將自身的數據包發給節點4，節點2在第6個時隙將自身產生的數據包發給節點3，節點3在第7個時隙將由節點2產生的數據包轉發給節點4，節點I在第10個時隙將自身產生的數據包發給節點3，節點3在第11個時隙將由節點I產生的數據包轉發給節點4。如圖6所示，圖6為本發明實施例提供的MDCD算法流程圖。具體過程如下步驟S601、網絡初始化。網絡初始化各個節點通過發送hello報文讓sink節點知道自己的喚醒周期n，將初始虛擬網格網絡拓展時間Λ設為節點Iii產生的數據包到達sink節點所需的最小時間中的最大值max=1 {!=}，其中，η為網絡中的總節點數。虛擬網格網絡拓展時間(VGN拓展時間)△即為數據收集持續時間。初始最大流fm設為O。其
中，& = — O[π步驟S602、將VGN拓展時間更新為k Ji。
步驟S603、判斷在殘留網絡Gf(A)中是否存在超級源節點s到超級sink節點d的增廣路徑P;若判斷結果為是(Yes)，則執行步驟S604，若判斷結果為是(No)，則執行步驟 S608。步驟S604、在增廣路徑P上增加流值f'。步驟S605、判斷流值f'是否滿足數據無衝突的限制條件。數據無衝突的限制條件可參照圖2a和圖2b。若判斷結果為是，則執行步驟S607，若判斷結果為否，則執行步驟S608。步驟S607、將流更新為f'，將殘留網絡更新為Gf' (Λ)，然後繼續執行步驟S603。步驟S608、fm更新為(G，s, d, c, Δ )的最大流，最優流路徑為P。 步驟S609、判斷fm是否小於η-1。若判斷結果為是，則執行步驟S6010，若判斷結果為否，則執行步驟S6011。步驟S6010、對k執行k=k+l運算。然後返回執行步驟S602。步驟S6011、在第k個節點喚醒周期內找到對應時間t最大的虛擬喚醒節點。步驟S6012、獲得最小數據收集時延Tmin等於所述最大的t。本發明的技術方案將由於節點喚醒周期造成的動態邏輯拓撲轉化成靜態的虛擬網格網絡，並基於虛擬網格網絡尋找最小時延無衝突的數據收集路徑，其採用無競爭的TDMA媒體接入機制，提高了數據收集的時效性，並保證了整個網絡的能效性，使網絡壽命最大化。上述僅為本發明的較佳實施例及所運用技術原理，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋在本發明的保護範圍內。
權利要求
1.一種低佔空比無線傳感器網絡中最小時延的數據收集方法，其特徵在於，包括如下步驟 A、根據實際網絡的物理拓撲G和各節點的喚醒周期π，將動態變化的邏輯拓撲轉化成靜態的、在時間上延拓的虛擬網格網絡； B、基於虛擬網格網絡，將初始虛擬網格網絡拓展時間△設為節點Iii產生的數據包到達Sink節點所需的最小時間中的最大值max丨/{!=}，其中，η為網絡中的總節點數； C、在虛擬網格網絡中尋找從超級源節點S到超級sink節點d之間滿足無衝突要求的最大流； D、判斷所述最大流是否等於源節點個數；若判斷結果為否，則將虛擬網格網絡在時間上繼續延拓，直到在找出的滿足無衝突要求的最大流等於源節點個數為止。
2.根據權利要求1所述的低佔空比無線傳感器網絡中最小時延的數據收集方法，其特徵在於，所述步驟A還包括 根據節點所承擔任務的不同，將節點分為三種葉子節點、中間節點和sink節點，其中，所述葉子節點只作為源節點發送數據包，所述中間節點既作為源節點發送數據包，又接收和轉發來自鄰居節點的數據包，所述Sink節點只作為目的節點接收數據包。
3.根據權利要求2所述的低佔空比無線傳感器網絡中最小時延的數據收集方法，其特徵在於，所述步驟A具體包括 Al、對於實際網絡的物理拓撲G中的每個節點IV在T時間內的任意時刻t，處於喚醒狀態的節點映射到虛擬網格網絡中在時間上延拓的虛擬喚醒節點Ni;t ； A2、在虛擬網格網絡中增加一個超級源節點s和超級sink節點d ； A3、當實際網絡的物理拓撲G中節點Iii是葉子節點，並且到節點η」存在有向邊時，如果節點Iii第一次t時刻喚醒，節點η」在時間t之後的P時刻喚醒，則在虛擬網格網絡中增加從Ni;t到Ν」，ρ的有向邊； A4、當實際網絡的物理拓撲G中節點Iii是中間節點，並且到節點η」存在有向邊時，如果節點Iii和η」的喚醒時間分別是t和p，並且t和P都在T時間內，p>t，則在虛擬網格網絡中增加從\t到的有向邊； A5、當實際網絡的物理拓撲G中節點Iii是sink節點時，則在虛擬網格網絡中建立其對應的所有虛擬喚醒節點到超級sink節點d之間的有向邊； A6、在虛擬網格網絡中建立從超級源節點s到所有源節點對應的第一個虛擬喚醒節點的有向邊。
4.根據權利要求3所述的低佔空比無線傳感器網絡中最小時延的數據收集方法，其特徵在於，所述步驟B中節點Iii產生的數據包到達sink節點所需的最小時間通過Dijkstra算法獲得。
5.根據權利要求4所述的低佔空比無線傳感器網絡中最小時延的數據收集方法，其特徵在於，所述步驟C包括通過Ford-Fulkerson最大流算法找到使數據收集時延最小的數據包傳輸路徑。
全文摘要
本發明公開一種低佔空比無線傳感器網絡中最小時延的數據收集方法，其包括如下步驟A、根據實際網絡的物理拓撲G和各節點的喚醒周期π，將動態變化的邏輯拓撲轉化成虛擬網格網絡。B、基於虛擬網格網絡，將初始虛擬網格網絡拓展時間Δ設為節點ni產生的數據包到達sink節點所需的最小時間中的最大值C、在虛擬網格網絡中尋找從超級源節點s到超級sink節點d之間滿足無衝突要求的最大流。D、判斷所述最大流是否等於源節點個數；若判斷結果為否，則將虛擬網格網絡在時間上繼續延拓，直到在找出的滿足無衝突要求的最大流等於源節點個數為止。本發明提高了數據收集的時效性，並且節點只在喚醒狀態進行數據接收，使網絡壽命最大化。
文檔編號H04W84/18GK103024859SQ201210505168
公開日2013年4月3日 申請日期2012年11月30日 優先權日2012年11月30日
發明者孫詠梅, 駱淑雲, 毛續飛, 紀越峰 申請人:無錫清華信息科學與技術國家實驗室物聯網技術中心, 北京郵電大學