無線傳感器網絡能耗均衡覆蓋調度及路由跨層設計方法
2023-09-13 00:34:10
無線傳感器網絡能耗均衡覆蓋調度及路由跨層設計方法
【專利摘要】本發明提供了一種無線傳感器網絡能耗均衡覆蓋調度及路由跨層設計方法。首先利用改進的ECCP冗餘節點判定算法，在考慮節點剩餘能量的基礎上，構造最小節點覆蓋集。隨後通過節點能耗速率來預測節點壽命，並確定激活的額外節點，使得網絡中節點能耗儘可能均衡。本發明提供的覆蓋調度算法將節點能耗速率作為調度依據，並以此建立了關聯路由協議的直接通道，可實現綜合覆蓋調度和路由的跨層設計。本發明提供了以定向擴散路由協議為例子的具體結合的方法。仿真結果顯示，應用本發明提供的覆蓋調度算法能夠顯著延長網絡壽命。
【專利說明】無線傳感器網絡能耗均衡覆蓋調度及路由跨層設計方法
【技術領域】
[0001]本發明屬於無線傳感器網絡應用層的覆蓋技術，以及綜合路由的跨層設計【技術領域】。
【背景技術】
[0002]無線傳感器網絡(Wireless Sensor Network, WSN)通常是由大量密集分布的微小傳感器節點通過自組織方式構成的。傳感器節點採用電池供電，不進行充電和電池更換，因此網絡生存期是WSN至關重要的性能指標。影響網絡生存期的主要有兩個因素，一是節點本身的能耗，二是節點能耗的均衡性。前者是指儘量減少節點的能耗，後者是指網絡節點的能耗應儘量平均，不至於部分節點能耗過快，而另外節點能耗較少。若不充分考慮節點能耗的均衡性，甚至可能出現某些節點因能量耗盡導致WSN無法正常工作，而其它節點剩餘90%以上能量的情況。
[0003]WSN通常由大量節點密集分布組成，節點布設存在較大的冗餘度，對於正常完成網絡的應用任務，並不需要所有節點均處於工作狀態。因此在滿足覆蓋要求的情況下，將節點分為若干不相交的節點集合，也叫覆蓋集，一個時間段只需要一個節點集合處於工作狀態即可。對於多個不同的覆蓋集，依據某種規則分別調度使用，稱之為覆蓋調度。
[0004]覆蓋調度有集中式和分布式兩種方式。集中式調度的效果較好，但要求了解全網所有節點的位置信息等，對於通常由成千上萬個節點組合的大規模WSN而言，缺乏足夠的實用意義。分布式調度只需獲取鄰居節點信息便可局部分布式進行，因此具有很好的擴展性。同時分布式調度減少了調度過程的通信開銷，有利於減少網絡能耗。從理論上而言，分布式調度的效果相對沒有集中式好，減少兩者的差別是分布式調度一直努力的目標。
[0005]覆蓋調度的本質就是利用WSN節點布設的冗餘度，在不同工作時間內更換工作節點，其主要依據就是處於工作狀態的節點的剩餘能量。在已有的覆蓋調度方法中，幾乎都是直接以節點剩餘能量為調度依據的，當節點最小剩餘能量到達某個預定的閾值時，便調度新的覆蓋集工作。
[0006]本發明在節點剩餘能量的基礎上考慮了能耗的速率，對節點剩餘能量進行預測，將能耗速率較快的節點更換掉，以更有效地實施節點覆蓋的調度，就此提供了一種新的能耗均衡的分布式WSN覆蓋調度算法(An Energy-Balance Coverage Configurat1nProtocol,EBCCP).在網絡技術中路由選擇對節點能耗的影響至關重要，因此本發明通過節點能耗將覆蓋調度與路由相結合，提供了綜合兩者的跨層設計方法，該方法適用於任何已有的WSN路由協議。基於定向擴散路由協議的仿真結果顯示，本發明提出的覆蓋調度算法可顯著延長網絡壽命。
【發明內容】
[0007]本發明的目的是提供基於節點能耗速率的無線傳感器網絡能耗均衡覆蓋調度算法，並與路由技術相結合，提供綜合路由和覆蓋調度的跨層設計方法。
[0008]為便於說明本發明的內容，首先結合圖1給出本發明中涉及的基本概念。
[0009]1..歐拉距離:區域A中的點p(x，y)和節點v(xv，yv)的歐拉距離
[0010]d(p, V) = yj(x -..V,.): + (j； — ν.):
[0011]2.鄰居節點集:節點V的鄰居節點集
[0012]
Niy) = {/ e ^ I d{vj.) < Rc,v /}
[0013]其中N是監測區域內的節點集，R。是節點V的通信半徑，d(v, i)是節點V和i之間的歐拉距離。
[0014]3.節點感知區域:節點V的感知區域
[0015]R(v) = {p e A|d(p, v) <RS}
[0016]其中A(邊界為C(A))為監測範圍，d(p, v)是點p和節點V之間的歐拉距離。
[0017]4.節點感知圓弧:節點V的感知圓弧
[0018]C (v) = {p e AI d (p, V) =Rj
[0019]5..內部交點集I (V):交點集
[0020]I (V) = {p IP e C (i)，P e C (j)，p e R (v)}
[0021]為節點V感知區域內的鄰居節點的感知圓的交點，其中i，j e N(V)，如圖1中圓形交點所示。
[0022]6.邊界交點集B (V):交點集
[0023]B (v) = {p IP e C(i), p e C(v)}
[0024]為節點V感知區域的邊界與V的鄰居節點的感知圓的交點,其中，i e N(V),如圖1中方形交點所示。
[0025]7.監測區域邊界交點集E(V):交點集
[0026]E (V) = {p IP e C (V)，P e C(A)}
[0027]為節點V的感知圓與目標區域A的邊界的交點，如圖1中稜形交點所示。
[0028]8..冗餘節點:如果某節點在監測區域內的感知區域被鄰居節點的感知區域完全覆蓋，則該節點為冗餘節點，可以進行休眠，如圖1中的節點V所示。
[0029]9.節點狀態:
[0030]Ready-on-duty:節點初始狀態；
[0031]On-duty:每一輪調度階段後的活躍節點狀態；
[0032]Ready-off-duty:滿足冗餘節點判斷條件的節點，準備進入休眠狀態；
[0033]Withdraw:構成最小覆蓋集後，所有處在非On-duty狀態的節點的狀態；
[0034]Off-duty:每一輪調度階段後的休眠節點狀態。
[0035]下面說明本發明的技術方案:
[0036]第一步判定冗餘節點
[0037]1.非邊界節點的冗餘判斷的步驟:
[0038](I)對任一個節點V，求出B (V),
[0039]I)如果不存在B(V)，則節點V不是冗餘節點，不可休眠；
[0040]2)若存在B (V)並且被覆蓋，則進入⑵；
[0041]若未被覆蓋，則V不是冗餘節點。
[0042](2)求I (V)，判斷I (V)是否被覆蓋:
[0043]I)若I (V)被覆蓋，則節點V是冗餘節點，可以進行休眠；
[0044]2)否則不是冗餘節點。
[0045]2.邊界節點的冗餘判斷步驟:
[0046](I)求 E (V),對 E (V)進行判定:
[0047]I)若E (V)被覆蓋，進入(2);
[0048]2)否則，V不是冗餘節點。
[0049](2)求 B (V)，
[0050]I)若不存在B (V),則V不是冗餘節點；
[0051]2)若存在，則對在監測區域內部的B(V)判斷是否被覆蓋:
[0052]若被覆蓋，則進入(3);
[0053]否則，V不是冗餘節點。
[0054](3)求I (V)，對在監測區域內部的I (V)判斷是否被覆蓋:
[0055]I)若被覆蓋，則節點V為冗餘節點，可以進行休眠；
[0056]2)否則不是冗餘節點。
[0057]第二步能耗均衡覆蓋調度
[0058]1.節點對自身到Sink點的跳數進行測量:
[0059](I) Sink點設置自己的跳數為0，並以節點的通信半徑R。為半徑廣播測量消息；
[0060](2)收到測量消息的節點延遲隨機時間Λ (t)後，比較收到消息中的跳數h(j為收到的消息編號)，設置自己的跳數為min (hj) +1 ；
[0061](3)這些節點再以R。為半徑廣播消息，直到所有節點都完成了測量。
[0062](4)所有節點的跳數置為Mi=I, 2...η)，跳數相同的節點的層數相同。
[0063]2.初始化能耗速率:
[0064](I)節點集V中所有節點初始為Ready-on-duty狀態，初始化自身的能耗速率sv=0 (v=l, 2，3...);
[0065](2)在隨機時間Tbadttjff後進行鄰居發現，包括鄰居的ID，位置，剩餘能量和所在的層數。
[0066](3)所有節點初始化能耗速率為O。
[0067]3.採用第一步冗餘節點判斷方法，
[0068](I)滿足休眠條件的節點進入Ready-off-duty狀態；
[0069](2)不滿足的直接進入On-duty狀態。
[0070]4.0n-duty狀態的節點組成最小節點覆蓋集:
[0071](I)所有 Ready-off-duty 狀態的節點退避 τν=((1_β) XEv/Em+ β Xrand(I) XTc)時間後，廣播Sleep信令，之後進入Withdraw狀態。其中Ev是自身的剩餘能量，Em是鄰居剩餘能量的最大值，β是隨[0，I]之間的隨機因子，Τ。是冗餘判定的總時間，rand (I)是[O, I]區間均勻分布的隨機數。
[0072](2)若在廣播Sleep消息之前收到Sleep消息,則更新鄰居節點表，刪除Withdraw狀態的鄰居節點，返回3。
[0073](3)經過多次循環，所有On-duty狀態的節點組成最小節點覆蓋集C。。
[0074]5.預測能耗速率，激活額外節點:
[0075](I)所有On-duty狀態的節點預測自身加入覆蓋集後的能耗速率值、..= Σ、'/?，其中V e Ctl, η為與節點V同一層(節點的層數標識見算法第一步)的能耗速率不為O的鄰居節點個數(包括節點V自身Xsi為與節點V同一層鄰居節點的能耗速率值(包括節點V自身上一輪的能耗速率)，且Si ^ O。
[0076](2)如果所有的Si=O,則不執行計算。然後，節點預測自身的生存時間tv=Ev/sv，其中Ev是節點的剩餘能量。
[0077]I)如果tv〈tth，則廣播Wake信令。Wake信令包含與自身處在同一層且剩餘能量最大的鄰居節點的ID號。
[0078]2)處於Withdraw狀態的節點收到信令後，檢查信令中的ID號與自身ID號是否相等:
[0079]若相等，則從Withdraw狀態進入On-duty狀態；
[0080]若不相等，則進入Off-duty狀態。
[0081](3)所有的On-duty狀態節點構成非最小節點覆蓋集C，並且新加入的額外節點只負責轉發數據，不負責收集數據，以節省能量。
[0082]第三步路由協議的結合應用
[0083]1.在第二步所得非最小節點覆蓋集上運行路由協議；
[0084]2.當覆蓋集中任一個節點的能量消耗完時，所有On-duty狀態的節點通過計算更新自身的能耗速率值，所有Off-duty狀態的節點把自身的能耗速率值置為0，同時更新V，返回第二步；
[0085]3.循環I和2，直到找不到一組節點能夠完全覆蓋監測區域時，網絡壽命終止。
[0086]本發明的有益效果:本發明提供了一種新的能耗均衡的分布式WSN覆蓋調度算法。首先利用改進的ECCP冗餘節點判定算法，在考慮節點剩餘能量的基礎上，構造最小節點覆蓋集。隨後，通過能耗速率預測來計算節點壽命，同時決定激活的額外節點，使得網絡中節點能耗儘可能的均衡。所得的調度算法可以與任何路由協議相結合。仿真結果顯示，本發明提供的覆蓋調度算法具有較好的性能，顯著延長網絡壽命。
【專利附圖】
【附圖說明】
[0087]圖1是與節點V的內部交點集、邊界交點集和監測區域邊界交點集；
[0088]圖2是冗餘節點判斷算法偽代碼；
[0089]圖3是覆蓋盲點的廣生不意圖
[0090]圖4是覆蓋調度過程的時間關係；
[0091]圖5是覆蓋調度過程中節點狀態轉換圖；
[0092]圖6是綜合覆蓋調度算法與路由的跨層實現過程。
【具體實施方式】
[0093]第一步判定冗餘節點
[0094]1.非邊界節點的冗餘判斷的步驟:
[0095](I)對任一個節點V,求出B(v),如果不存在B(v),則節點V不是冗餘節點，不可休眠；若存在B(V)並且被覆蓋，則進入(2);若未被覆蓋，則V不是冗餘節點。
[0096](2)求I (V)，判斷I (V)是否被覆蓋，若I (V)被覆蓋，則節點V為冗餘節點，可以進行休眠；否則不是冗餘節點。
[0097]2.邊界節點的冗餘判斷步驟:
[0098](I)求E(v)，對E(V)進行判定，若E(V)被覆蓋，進入(2);否則，V不是冗餘節點。
[0099](2)求B (V)，若不存在B (V)，則V不是冗餘節點，若存在，則對在監測區域內部的Β(ν)判斷是否被覆蓋，若被覆蓋，則進入(3)，否則，V不是冗餘節點。
[0100](3)求I (V)，對在監測區域內部的I (V)判斷是否被覆蓋，若被覆蓋，則節點V為冗餘節點，可以進行休眠；否則不是冗餘節點。
[0101]圖2給出了上述過程實施的偽代碼。
[0102]第二步能耗均衡覆蓋調度
[0103]1.節點對自身到Sink點的跳數進行測量:
[0104](I) Sink點設置自己的跳數為0，並以節點的通信半徑Re為半徑廣播測量消息。
[0105](2)收到測量消息的節點延遲隨機時間Λ (t)後，比較收到消息中的跳數hj (j為收到的消息編號)，設置自己的跳數為min(hp+Ι，這些節點再以R。為半徑廣播消息，直到所有節點都完成了測量。所有節點的跳數置為hi(i=l，2...η)，跳數相同的節點的層數相同。延遲Λ (t)是為了防止相鄰節點同時廣播消息而產生衝突。
[0106]2.節點集V中所有節點初始為Ready-on-duty狀態，初始化自身的能耗速率sv=0 (v=l, 2，3...),在隨機時間Tbad5t5ff後進行鄰居發現,包括鄰居的ID,位置,剩餘能量和所在的層數。所有節點初始化能耗速率為O。延後Tbadttjff是為了避免多個節點同時廣播導致道衝突和消息丟失。
[0107]3.採用第一步冗餘節點判斷方法,滿足休眠條件的節點進入Ready-off-duty狀態。不滿足的直接進入On-duty狀態。
[0108]4.0n-duty狀態的節點組成最小節點覆蓋集:
[0109](I)所有 Ready-off-duty 狀態的節點退避 τν=((1_β) XEv/Em+ β Xrand(I) XTc)時間後，廣播Sleep信令，之後進入Withdraw狀態。其中Ev是自身的剩餘能量，Em是鄰居剩餘能量的最大值，β是隨[0，I]之間的隨機因子，Τ。是冗餘判定的總時間，rand (I)是[0,1]區間均勻分布的隨機數。引入隨機數是為了避免剩餘能量相同的節點選擇相同的時延。退避τν是為了剩餘能量少的節點休眠的機會更大，達到平衡網絡內節點能耗的作用。同時也能也保證了鄰居節點並發休眠可能出現的覆蓋盲區。
[0110]下面結合圖3進一步說明。如圖3所示，節點I和2均滿足冗餘覆蓋條件，但節點I是以節點2工作為條件的，節點2是以節點I工作為條件的，若兩者同時進入休眠狀態就會導致覆蓋盲點的產生。
[0111](2)若在廣播Sleep消息之前收到Sleep消息,則更新鄰居節點表,刪除Withdraw狀態的鄰居節點，返回3。
[0112](3)經過多次循環，所有On-duty狀態的節點組成最小節點覆蓋集C。。
[0113]5.預測能耗速率，激活額外節點:
[0114](I)所有On-duty狀態的節點預測自身加入覆蓋集後的能耗速率值= Σ '.^，其中V e Ctl, η為與節點V同一層(節點的層數標識見算法第一步)的能耗速率不為O的鄰居節點個數(包括節點V自身Xsi為與節點V同一層鄰居節點的能耗速率值(包括節點V自身上一輪的能耗速率)，且Si ^ O。
[0115](2)如果所有的Si=O,則不執行計算。然後，節點預測自身的生存時間tv=Ev/sv，其中Ev是節點的剩餘能量。
[0116]I)如果tv〈tth,則廣播Wake信令。Wake信令包含與自身處在同一層且剩餘能量最大的鄰居節點的ID號。
[0117]2)處於Withdraw狀態的節點收到信令後，檢查信令中的ID號與自身ID號是否相坐寸，
[0118]若相等，則從Withdraw狀態進入On-duty狀態；
[0119]若不相等,則進入Off-duty狀態。
[0120](3)所有的On-duty狀態節點構成非最小節點覆蓋集C，並且新加入的額外節點只負責轉發數據，不負責收集數據，以節省能量。
[0121]圖4進一步提供上述調度過程具體的內容及時間關係。調度階段包括鄰居發現、冗餘節點判定和額外節點激活三個子階段。在鄰居發現階段，節點通過廣播Hello消息與鄰居節點交換信息獲取鄰居節點的ID、位置、節點跳數和能量信息，建立鄰居節點表。在此基礎上，節點判定自身是否滿足冗餘條件，若不滿足冗餘條件，則節點在本輪的穩定階段保持活躍狀態，若節點滿足冗餘條件，則進入更新鄰居表和重新判斷階段，最後所有活躍狀態的節點依據規則激活額外節點，所有活躍狀態的節點負責對目標區域進行感知、監測以及數據傳輸。所有不滿足條件的節點進入休眠狀態，直到下一個調度階段。通常穩定階段時間Tw遠大於調度階段時間Ts，以降低算法開銷。
[0122]圖5具體給出了調度過程中節點狀態的轉換圖。
[0123]第三步與路由協議結合應用
[0124]本發明提供的覆蓋調度算法可以應用於任意路由協議，原因是路由與覆蓋調度的關係是通過節點能耗這一一般性性過程實現的。
[0125]下面以定向擴散(Directed Diffus1n, DD)路由協議為例具體說明。
[0126]1.應用第一步和第二步算法,選出工作組節點。
[0127]2.Sink節點廣播Interest,按照DD協議建立路由。
[0128]3.數據收集和數據傳輸階段，到達一輪時間後，轉入到1，循環執行。
[0129]圖6具體給出了調度算法與路由協議具體的結合應用過程。
【權利要求】
1.一種無線傳感器網絡覆蓋中冗餘節點的判定方法，其特徵是: 1)非邊界節點的冗餘判斷的步驟: (1)對任一個節點V，求出B(V)，如果不存在B(V)，則節點V不是冗餘節點，不可休眠；若存在B (V)並且被覆蓋，則進入(2);若未被覆蓋，則V不是冗餘節點； (2)求I(V)，判斷I (V)是否被覆蓋，若I (V)被覆蓋，則節點V是冗餘節點，可以進行休眠；否則不是冗餘節點； 2)邊界節點的冗餘判斷步驟: (1)求E(V)，對E(V)進行判定，若E(V)被覆蓋，進入(2);否則，V不是冗餘節點； (2)求B(V)，若不存在B (V)，則V不是冗餘節點；若存在，則對在監測區域內部的B (V)判斷是否被覆蓋，若被覆蓋，則進入(3);否則，V不是冗餘節點； (3)求I(V)，對在監測區域內部的I(V)判斷是否被覆蓋，若被覆蓋，則節點V為冗餘節點，可以進行休眠；否則不是冗餘節點。
2.基於節點能耗速率的無線傳感器網絡能耗均衡覆蓋調度算法，其特徵是: 1)節點對自身到Sink點的跳數進行測量: (1)Sink點設置自己的跳數為O，並以節點的通信半徑R。為半徑廣播測量消息； (2)收到測量消息的節點延遲隨機時間Λ(t)後，比較收到消息中的跳數h(j為收到的消息編號)，設置自己的跳數為min (hj) +1，這些節點再以R。為半徑廣播消息，直到所有節點都完成了測量；所有節點的跳數置為hi(i=l，2...η)，跳數相同的節點的層數相同； 2)節點集V中所有節點初始為Ready-on-duty狀態，初始化自身的能耗速率sv=0 (v=l, 2, 3...);在隨機時間Tbaektjff後進打鄰居發現,包括鄰居的ID,位直,剩餘能量和所在的層數；所有節點初始化能耗速率為O ; 3)採用第一步冗餘節點判斷方法，滿足休眠條件的節點進入Ready-off-duty狀態；不滿足的直接進入On-duty狀態； 4)On-duty狀態的節點組成最小節點覆蓋集: (1)所有Ready-off-duty 狀態的節點退避 τ ν=((1-β ) XEv/Em+3 Xrand(I) XTc)時間後，廣播Sleep信令，之後進入Withdraw狀態；其中Ev是自身的剩餘能量，Em是鄰居剩餘能量的最大值，β是隨[O, I]之間的隨機因子，Tc是冗餘判定的總時間，rand (I)是[O, I]區間均勻分布的隨機數； (2)若在廣播Sleep消息之前收到Sleep消息,則更新鄰居節點表,刪除Withdraw狀態的鄰居節點，返回3)； (3)經過多次循環，所有On-duty狀態的節點組成最小節點覆蓋集C。； 5)預測能耗速率，激活額外節點: (1)所有On-duty狀態的節點預測自身加入覆蓋集後的能耗速率值\= Σ.、./?，其中V e C0, η為與節點V同一層(節點的層數標識見算法第一步)的能耗速率不為O的鄰居節點個數(包括節點V自身Xsi為與節點V同一層鄰居節點的能耗速率值(包括節點V自身上一輪的能耗速率)，且Si^O; (2)如果所有的Si=O,則不執行計算；然後，節點預測自身的生存時間tv=Ev/sv，其中Ev是節點的剩餘能量； 如果tv〈tth，則廣播Wake信令；Wake信令包含與自身處在同一層且剩餘能量最大的鄰居節點的ID號； 處於Withdraw狀態的節點收到信令後，檢查信令中的ID號與自身ID號是否相等， 若相等，則從Withdraw狀態進入On-duty狀態； 若不相等，則進入Off-duty狀態； (3)所有的On-duty狀態節點構成非最小節點覆蓋集C，並且新加入的額外節點只負責轉發數據，不負責收集數據，以節省能量。
3.結合權利要求1和權利要求2算法的跨層路由設計方法，其特徵是: 1)在權利要求1和權利要求2算法所得非最小節點覆蓋集上運行路由協議； 2)當覆蓋集中任一個節點的能量消耗完時，所有On-duty狀態的節點通過計算更新自身的能耗速率值，所有Off-duty狀態的節點把自身的能耗速率值置為0，同時更新V，返回第二步； 3)循環執行I)和2)，直到找不到一組節點能夠完全覆蓋監測區域時，網絡壽命終止。
【文檔編號】H04W52/02GK104168631SQ201410004743
【公開日】2014年11月26日 申請日期:2014年1月6日 優先權日:2014年1月6日
【發明者】熊慶旭, 付寅飛 申請人:北京航空航天大學