穩定節能分群方法
2023-12-03 16:36:06
專利名稱：穩定節能分群方法
技術領域：
本發明涉及一種形成和保持分層分布式結構的網絡分群方法，特別是一種可提供穩定網絡分群結構、保證節點能量均衡消耗和延長網絡整體生存時間的穩定節能分群方法。
背景技術：
移動自組織網絡中，在進行通信之前需要經過自組織過程形成預定的網絡結構，以便實現對通信的支持、控制和管理。這些網絡結構通常分為完全分布式、分層分布式和集中式三類。其中，為了支持自組織網絡的無線、多跳、移動特性，分層分布式結構(即分群結構)是最有效的控制和管理方法。分群結構是利用分群協議把整個網絡中的所有節點劃歸到多個相連的以群首(CH)為中心的群組，由群首負責群組內的控制和管理，其優點包括提高信道的空間復用效率、減少路由和網絡控制管理開銷、易實現擁塞控制和流量均衡、為多媒體業務提供保證服務質量(QoS)的傳輸、易實現網絡的移動性管理和局部同步、適於擴展擁有大量節點的自組織網絡等。
移動自組織網絡中，節點的移動、加入、離去或失效等情況造成了通信鏈路的斷接和網絡拓撲的變化，這在分群之後表現為節點經常加入或離開群，影響分群結構乃至網絡通信的穩定。更為嚴重的情況是，劇烈的節點移動導致頻繁的群首更替和分群的分解、重構，引入了較大的通信和計算開銷，進而嚴重影響其他網絡性能，如通信所用路由、端到端吞吐量、時延、分組丟棄率和各類資源管理利用等。因此對於分層結構，最關鍵的問題是如何收集、運用拓撲信息，快速建立預定的分群結構，實現在高速移動環境下的動態穩定保持。這個問題由分群方法和分群保持方法兩個方面來解決，分群方法是在探測拓撲的基礎上形成網絡的分群結構，主要是群首選擇過程，而分群保持方法則是在節點移動情況下保持穩定、可連續通信的分群網絡。分群方法和分群保持方法通常是利用節點的某些特徵或因素作為分群及分群保持的依據，即把這些特徵或因素映射成一種權重，當某一節點的權重在局部最大時，該節點就被選為群首。現有的分群方法和分群保持方法分別為(1)最小本徵號分群(Lowest ID)方法該方法中，鄰節點中具有最小ID的節點被選作群首，在兩個群首相遇時保留最小ID的群首。該方法僅需要兩輪控制消息的交換即可建立分群結構，具有分群速度較快、分群保持過程簡單等優點。但該方法在群首選舉和分群保持過程中沒有考慮節點移動因素的影響，使最小ID的節點由於充當群首而消耗更多的能量，如果局部最小ID的節點移動很快，群分解和重構的頻率就很大，會導致網絡性能的惡化。
(2)最大連接度分群(Max Degree)方法該方法利用最大連接度(即節點的鄰節點數目)的標準來分群並進行分群保持，其目標是儘量將控制管理權交給鄰節點較多的節點。該方法的優點在於分群的數目較少，減少了分組傳輸時延，但缺點是降低了信道的空分復用。同時，當群內節點數目較多時，平均到每個節點的吞吐量將會減少，使群首更易成為網絡通信的瓶頸，網絡的整體效能將隨之降低。此外，由於該分群方法執行前必須獲得節點的連接度，這需要多交換一輪自組織消息，因此該方法還存在組網時間較長、開銷較大、群首和成員穩定性差等缺陷。
(3)分布式移動自適應分群(DMAC)方法該方法根據節點事先指定的權重值，在鄰節點中具有最大權重的節點被選為群首，並在此之後結合鏈路失效、建立和節點加入事件進行分群保持。但該方法沒有考慮節點移動性，高權重群首的高速移動會嚴重影響整個網絡的性能，並且算法中所採用的權重值是事先指定，沒有說明其意義以及如何反映網絡中節點的特性。
(4)非確定-確定混合分群(UC-CM)方法該方法引入「優先級」參數來進行分群和分群保持，節點的優先級越高，越優先成為群首。該方法同樣因為沒有考慮節點移動因素影響，當群首移動較快時，群分解和重構的頻率就很大，導致網絡性能的惡化。
(5)基於接入的分群(ABCP)和基於信道接入的自組織分群(CABSOC)方法該方法從信道接入的角度考慮分群協議，從一開始節點就試圖利用所設計的信道接入方法成為群首或加入已經存在的群，當群首相遇、進入非活動態、異常情況(如節點失效、消息丟失等)等事件出現時進行相關的分群保持。由於前者需要利用周期性的HELLO消息或heart-beat詢問應答消息來表明群首和普通節點的存在，後者需要各節點周期性廣播信標(Beacon)來申明本節點的存在，存在組網時間較長、開銷較大等缺陷。
(6)基於移動性機制的分群(MOBIC)方法該方法為克服上述方法未考慮節點移動因素所的技術缺陷，把連續收到分組的接收信號功率比作為評估節點間相對移動性的權重，並利用該權重來選擇群首和保持分群。由於該方法的前提假設是無線信號傳播信道中不存在多徑和衰落影響，在節點移動性方面僅考慮了節點單體的移動性，並且需要相距兩跳節點的信息，使該方法在實際應用中仍存在開銷較大、群首和成員穩定性差等缺陷。
(7)基於權值分群(WCA)方法該方法考慮了節點作為群首所能支持的最佳成員節點數、節點的傳輸功率、移動性及剩餘能量狀態，在鄰居範圍內選擇具有最小權值的節點成為群首節點，分群維保持也是通過事件驅動方式調用分群方法實現。但是該方法所提出的各個權值分量不能很好體現節點的對應特徵，權值的計算需要進行大量的信息交換及計算，帶來大量開銷。
綜上所述可以看出，上述現有技術的分群保持方法都是在網絡拓撲發生變化後被動地觸發網絡中節點信息的收集，再通過大量的信息交互開銷才能夠獲取分群維護所需的網絡節點狀態信息，是完全的被動維護，存在效率低、開銷大等問題。另外，上述現有技術的分群方法要麼沒有考慮節點移動性，要麼雖然考慮了節點移動性，但不能很好地體現節點的對應特徵。一方面只是在節點移動、入網、退網或失效而造成拓撲發生變化後去應對這些變化，而節點的移動是造成拓撲變化、影響分群結構穩定的主要因素，因此相關方法不能從根本上有效保證分群結構的穩定；另一方面在實際應用中存在大量信息交換及計算開銷，分群結構形成不夠迅速，並且存在能量消耗不均衡、網絡整體壽命短等技術缺陷。
發明內容
本發明的目的是針對現有分群和分群保持方法中存在的分群結構被動維護、穩定性差、少數節點移動導致網絡性能惡化、開銷較大以及能量消耗不均衡等技術缺陷，提供一種穩定節能分群方法，在高速移動環境下可以有效的保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡整體壽命。
為了實現上述目的，本發明提供了一種穩定節能分群方法，包括步驟步驟10、設定群首輪詢時鐘；步驟20、啟動輪詢時鐘；步驟30、判斷輪詢時鐘是否超時，超時時執行步驟40，未超時則執行步驟30；步驟40、群首輪詢群內成員節點，獲取成員節點的相對移動性值、相對剩餘能量狀況值和局部節點度值，計算各成員節點的選擇權值；步驟50、群首判斷其選擇權值是否低於選擇閾值，是則執行步驟60，否則執行步驟70；步驟60、群首激活群內候選節點，候選節點發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成；
步驟70、群首選擇候選節點，候選節點監視群首狀態，執行步驟20；其中，所述步驟40中節點的選擇權值為Wi＝w1Si+w2Pi+w3Ri，式中，i表示節點ID，Wi表示節點i的選擇權值，Si表示節點i相對於其鄰居節點的相對移動性值，Pi表示節點i的相對剩餘能量狀況值，Ri表示節點i的局部節點度值，係數w1，w2和w3是相應參數的權重值，且∑wi＝1。
其中，所述步驟70具體為步驟71、群首選擇具有最大選擇權值的成員節點為候選節點；步驟72、群首廣播發布消息，公布候選節點ID和各成員節點選擇權值；步驟73、候選節點定期檢查是否收到群首節點廣播的周期性消息，收到時執行步驟20，未收到時執行步驟74；步驟74、候選節點向群首發送詢問消息；步驟75、候選節點判斷是否收到群首的確認消息，收到時執行步驟20，否則執行步驟76；步驟76、候選節點判斷詢問計數值是否超過詢問計數閾值，是則執行步驟77，否則將詢問計數值加1後執行步驟74；步驟77、候選節點自動激活，發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成，返回執行步驟20。
在上述技術方案中，所述步驟30中當判斷輪詢時鐘未超時時，執行步驟步驟31、網絡拓撲自動監視，探測分群結構變化；步驟32、判斷分群結構是否變化，當分群結構變化時執行步驟33，否則執行步驟30；步驟33、根據不同事件類型，調用相應處理程序進行分群結構更新，更新結束後執行步驟30。
所述步驟33中調用相應處理程序進行分群結構的更新包括節點加入處理、節點退出處理、群首相遇處理、節點脫離群首處理或成員節點失效處理。
在上述技術方案中，還包括對網絡進行初始化分群的步驟，具體為
步驟1、網絡中所有節點廣播消息，所述消息包含節點ID和剩餘能量值；步驟2、每個節點根據收到消息生成一個鄰居節點表；步驟3、每個節點判斷其剩餘能量值是否大於能量閾值，是則執行步驟4，否則執行步驟6；步驟4、所述節點判斷其節點ID是否在鄰居範圍未分群節點中為最小，是則執行步驟5，否則執行步驟7；步驟5、所述節點發送群首消息，宣布建立新群，所述新群ID為該節點的ID，穩定節能分群完畢；步驟6、所述節點等待，直至收到來自鄰居節點的群首消息，節點加入該群成為成員節點，穩定節能分群完畢；步驟7、所述節點判斷是否在一設定時間內收到來自鄰居節點的群首消息，收到時執行步驟8，否則返回執行步驟4；步驟8、節點加入該群成為成員節點，穩定節能分群完畢。
本發明穩定節能分群方法針對節點移動性對分群結構穩定性的劇烈影響，提出了一種通過定期輪詢方式監視網絡節點狀態以更新分群結構、對分群結構進行必要維護的穩定節能分群維護方法，還提出了一種節能初始化分群方法。
在初始狀態下，本發明採用節能初始化分群方法對網絡進行初始化分群，所有節點最終決定其角色，獲得一個覆蓋全網的分群結構。方法中的群首節點選舉是基於節點的ID和節點的剩餘能量值P，當節點的剩餘能量值P大於能量閾值Pthreshold時，並且其節點ID在其鄰居範圍內是最小的，那麼該節點將被選舉為群首節點，其鄰居節點都加入到其中成為成員節點。本發明群首節點選舉考慮了節點剩餘能量值P，且作為衡量節點是否具備成為群首的先決條件，因此本發明不僅具有僅需兩輪控制消息的交換即可建立分群結構，分群速度較快、分群保持過程簡單等優點，而且由於在群首選舉階段考慮了節點的剩餘能量狀態，避免了某些剩餘能量低的節點擔當群首以及部分節點長期擔當群首的可能性，確保了節點擔當群首的公平性，從而均衡了能量消耗，作為群首的節點不會因為能量消耗大使分群結構的穩定性在短時間內變差，因此消除了現有技術群分解和重構頻率加大、網絡性能惡化等技術缺陷。
在分群結構維護階段，本發明採用通過定期輪詢方式監視網絡節點狀態以更新分群結構、對分群結構進行必要維護的穩定節能分群維護方法，同時提出了一種選擇權值概念，作為群首更換時選舉群首的判據。定期輪詢方式是一種主動的分群結構維護方式，當原群首不能承擔群首角色時迅速激活備用群首擔當群首角色，可以及時適應節點運動和群首能量消耗所帶來的分群結構變化，有效的保證分群結構的穩定性。本發明根據節點的選擇權值大小為每一個群首選舉一個候選節點作為備用群首，選擇權值考慮了節點的相對移動性、相對剩餘能量狀況和局部節點度，並通過權重值將上述節點特徵有機地結合起來。將選擇權值作為群首更換時選舉群首的標準，使本發明可有效保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡的整體壽命。
另外，本發明在採用定期輪詢方式對網絡狀態信息進行更形，進而對分群結構進行必要維護的同時，通過對網絡拓撲自動監視和分群結構變化探測，針對群首相遇、成員節點脫離原群、節點的加入與退出等情況設計了相應的處理程序，將分群結構的定期輪詢和隨時維護有機地結合在一起，使得本發明具有寬廣的適應性。
下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。
圖1為本發明穩定節能分群方法流程圖；圖2為本發明實施例一的流程圖；圖3、圖4為本發明實施例二的流程5為本發明節點加入處理流程圖；
圖6為本發明節點退出處理流程圖；圖7為本發明群首相遇處理流程圖；圖8為本發明節點脫離群首處理流程圖；圖9為本發明成員節點失效處理流程圖；圖10為本發明初始化分群流程圖。
具體實施例方式
圖1為本發明穩定節能分群方法流程圖，具體為步驟10、設定群首輪詢時鐘；步驟20、啟動輪詢時鐘；步驟30、判斷輪詢時鐘是否超時，是則執行步驟40，否則執行步驟30；步驟40、群首輪詢群內成員節點，獲取成員節點的相對移動性值、相對剩餘能量狀況值和局部節點度值，計算各成員節點的選擇權值；步驟50、群首判斷其選擇權值是否低於選擇閾值，是則執行步驟60，否則執行步驟70；步驟60、群首激活群內候選節點，候選節點發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成；步驟70、群首選擇候選節點，候選節點監視群首狀態，執行步驟20；上述技術方案實際上是一種穩定節能分群維護方法，群首周期性輪詢它的成員節點以獲得節點的相對移動性值S、相對剩餘能量狀況值P和局部節點度值R，然後群首為自己及它的所有成員節點計算選擇權值W，並選舉具有最大選擇權值的成員節點作為它的候選節點。當群首的選擇權值降低至選擇閾值Wthreshold以下，以至於它不能擔當群首角色時，原群首會發送激活消息激活候選節點成為新的群首節點。此時，新群首節點通過廣播群首消息宣布自己的新角色，收到這個群首消息後，它的鄰居節點，包括原來的群首節點都通過發送加入消息加入新群或者加入到鄰近群中，新的分群結構形成。
本發明穩定節能分群方法針對節點移動性對分群結構穩定性的劇烈影響，不僅提出了一種通過定期輪詢方式監視網絡節點狀態以更新分群結構、對分群結構進行必要維護的穩定節能分群維護方法，還提出了一種選擇權值概念，作為群首更換時選舉群首的判據。本發明穩定節能分群維護方法是一種主動的分群結構維護方式，突破了現有技術只有在分群結構出現問題時才進行相應處理的被動維護方式。在移動自組織網絡中，節點由於充當群首而消耗更多的能量，節點的高速運動將導致分群結構穩定性很差，因此在分群結構穩定性已經惡化的情況進行被動維護，不僅引入了大量控制開銷，而且很難得到穩定的分群。本發明提出的定期輪詢方式則有效地解決了現有技術上述技術問題，本發明根據節點選擇權值大小為每一個群首選舉一個候選節點作為備用群首，當原群首不能承擔群首角色時迅速激活備用群首擔當群首角色，可以及時適應節點移動所帶來的分群結構變化，有效地保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡的整體壽命。
本發明選擇權值定義為Wi＝w1Si+w2Pi+w3Ri式中，i表示節點ID，Wi表示節點i的選擇權值，Si表示節點i相對於其鄰居節點的相對移動性值，Pi表示節點i的相對剩餘能量狀況值，Ri表示節點i的局部節點度值，係數w1、w2和w3是相應參數的權重值，且∑wi＝1。。
本發明選擇權值Wi考慮了節點的相對移動性、相對剩餘能量狀況和局部節點度，並通過權重值將上述節點特徵有機地結合起來，根據系統要求和網絡的實際特點可以動態調節權重值以適應不同的系統要求。節點由於充當群首會消耗更多的能量，相對剩餘能量狀況可以很好地反映節點的能量狀態，保證在一定範圍內選舉出具有較大能量的節點成為群首，避免了相對剩餘能量較低的節點擔當群首角色的可能性，因此均衡了網絡中節點能量的消耗，延長了網絡壽命；節點的高速運動將導致節點連接度的頻繁變化，同時在維護過程中將會引入大量的控制開銷，本發明選擇權值引入節點的相對移動性可以很好地保證分群結構的穩定性；節點的局部節點度反映該節點與原群中成員節點的連結狀況，該值越大，則表示對應節點與原群中越多的成員節點相連結，當該節點成為群首節點時引起的分群結構變化與原分群結構相比最小，因此可以很好地保持原來的分群結構，提高了穩定性，並且減少了因成員節點更換群首帶來的交互開銷。將選擇權值作為群首更換時選舉群首的標準，使本發明可有效保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡的整體壽命。由於本發明中採用了一種主動輪詢的方式監視網絡節點狀態以便對分群結構進行維護，所需要的信息都能夠通過定期輪詢獲得，無需通過被動交互的方式進行相關信息的獲取，在很大程度上減少了信息的交換，降低了開銷。同時，由於採用選擇權值作為群首更換時選舉群首的標準，充分考慮了引起網絡拓撲變化的因素，提高了分群結構的穩定性，從而減少了分群維護過程中分群結構重建的次數，也在很大程度上降低了開銷。
本發明可根據系統要求和網絡的實際特點對權重值w1、w2和w3進行動態調節，以適應不同的系統要求。例如，對於無線傳感器網絡，由於節點移動性很低，影響分群結構的主要因素為節點的能量狀態，可以設置w1＝0.05～0.10，w2＝0.80～0.90，w3＝0.05～0.10；對於高速移動環境下的無線自組織網絡，影響分群結構的主要因素為節點的移動性，並且節點的電源可以更換，能量不再是主要考慮的因素，可以設置w1＝0.45～0.55，w2＝0.05～0.10，w3＝0.40～0.50。
下面通過具體實施例進一步說明本發明技術方案。
實施例一圖2為本發明實施例一的流程圖。如圖2所示，本實施例的技術方案是在圖1所示技術方案基礎上，所述步驟70具體為步驟71、群首選擇具有最大選擇權值的成員節點為候選節點；
步驟72、群首廣播發布消息，公布候選節點ID和各成員節點選擇權值；步驟73、候選節點定期檢查是否收到群首節點廣播的周期性消息，收到時執行步驟20，未收到時執行步驟74；步驟74、候選節點向群首發送詢問消息；步驟75、候選節點判斷是否收到群首返回的確認消息，收到時執行步驟20，否則執行步驟76；步驟76、候選節點判斷詢問計數值是否超過詢問計數閾值，是則執行步驟77，否則將詢問計數值加1，返回執行步驟74；步驟77、候選節點自動激活，發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成，返回執行步驟20。
本實施例具體處理過程為在分群維護階段，群首周期性輪詢它的普通成員節點以獲得節點的相對移動性值S，節點相對剩餘能量狀況值P和局部節點度值R，然後，群首為自己及它的所有成員節點計算選擇權值W。當群首節點選擇權值下降到選擇閾值Wthreshold以下，以至於它不能擔當群首角色時，原群首會發送激活消息激活候選節點成為新的群首節點。此時新群首節點通過廣播群首消息宣布自己的新角色。收到這個群首消息後，它的鄰居節點，包括原來的群首節點都通過發送加入消息加入新群或者加入到鄰近群中。如果群首節點選擇權值在選擇閾值Wthreshold以上，說明它仍能擔當群首角色。無論是原群首繼續擔當群首角色還是新群首取代原群首，原群首或新群首都選舉具有最大選擇權值的成員節點作為它的候選節點，並廣播包含候選節點ID和所有節點選擇權值的候選節點消息，候選節點作為群首節點的備用存在。之後，候選節點通過檢查是否收到群首節點廣播的周期性消息，可以監視群首狀態，當候選節點在一段時間內不能收到群首消息時，它會發送一個詢問消息。如果群首還存在，它將會發送一個確認消息。當嘗試一定次數後還是不能收到確認時，候選節點將會認為原群首已經消失，因此候選節點廣播群首消息，宣布成為新群首。收到這個群首消息的節點如果不能和它的原群首通信，它們將會選擇加入到新群中或者加入到其他相鄰群中。
本實施例技術方案進一步確保了分群結構的穩定性，特別是當群首出現問題時，候選節點可以及時判斷出群首是否存在，在高速移動環境下從根本上有效保證分群結構的穩定。
實施例二本實施例的技術方案是在圖1、圖2所示技術方案基礎上，所述步驟30中，當判斷輪詢時鐘未超時時，執行下述步驟步驟31、網絡拓撲自動監視，探測分群結構變化；步驟32、判斷分群結構是否變化，當分群結構變化時執行步驟33，否則執行步驟30；步驟33、根據不同事件類型，調用相應處理程序進行分群結構更新，更新結束後執行步驟30。
本實施例是在定期輪詢方式更新更新網絡狀態信息，進而更新分群結構、對分群結構進行必要維護的同時，通過對網絡拓撲自動監視和分群結構變化探測，並根據監視和探測的結果，對發生變化的分群結構進行調用相應處理程序進行分群結構更新。該技術方案將分群結構的定期輪詢和隨時維護有機地結合在一起，主動輪詢可以定期獲得所需的信息，而其他較小的網絡拓撲變化被隨時維護及時處理掉，既提高了分群結構的穩定性，又減少了分群結構重建次數。
圖3和圖4分別示意了本實施例相應的流程圖，具體處理過程為設定群首輪詢時鐘後，群首隻有在輪詢時鐘超時後才開始輪詢操作，如果時間未到，系統則對網絡拓撲自動監視和分群結構變化探測，判斷分群結構是否變化，如果有變化，則根據不同事件類型調用相應處理程序進行分群結構更新，更新結束後繼續網絡拓撲自動監視和分群結構變化探測。其中事件是指觸發分群結構變化的相應事件，本發明根據導致分群結構變化的事件類型設置了相應的處理程序，以及時對分群結構進行更新。
實施例三本實施例是在實施例二技術方案基礎上，步驟33中調用相應處理程序進行分群結構更新包括節點加入處理。圖5為本發明節點加入處理流程圖，具體為步驟A1、新節點加入到網絡中；步驟A2、新節點交替監聽網絡中的所有信道；步驟A3、新節點根據監聽結果加入到具有最大選擇權值的群首所在的群中，成為該群的成員節點。
當有節點加入到網絡中時，它需要交替監聽網絡中的所有信道，基於監聽結果，節點會選擇加入到具有最大選擇權值的群首所在的群成為其普通成員節點。
實施例四本實施例是在實施例二技術方案基礎上，步驟33中調用相應處理程序進行分群結構更新包括節點退出處理。圖6為本發明節點退出處理流程圖，具體為步驟B1、退出節點向群首節點發送退網請求；步驟B2、群首節點向該退出節點發送一個離開確認信息，並從其成員列表中刪除所述退出節點；步驟B3、退出節點收到群首回復的離開確認信息後，正常離開網絡。
當有節點要退出網絡時，它會發送退網請求通知群首節點，群首節點會向該節點發送一個離開確認信息並且其從成員列表中刪除該節點，在收到群首回復的確認信息後，該節點就可以正常離開網絡。
實施例五本實施例是在實施例二技術方案基礎上，步驟33中調用相應處理程序進行分群結構更新包括群首相遇處理。圖7為本發明群首相遇處理流程圖，具體為
步驟C1、節點運動引起的網絡拓撲變化使兩個群首相遇；步驟C2、判斷一個群首是否可以包含另一群首及其成員節點，是則執行步驟C3，否則執行步驟C4；步驟C3、兩個群合併，形成新群，群首相遇處理完畢；步驟C4、分群結構保持不變，群首相遇處理完畢。
當兩個群首相遇時，如果一個群首及它的鄰居節點所形成的集合能夠包含另一個群首和它的普通成員節點，那麼者兩個群將會合併，能夠覆蓋原來的兩個的所有普通成員節點的群首成為新群首，另一個群消失。其他情況下，分群結構保持不變。
實施例六本實施例是在實施例二技術方案基礎上，步驟33中調用相應處理程序進行分群結構更新包括成員節點脫離群首處理。圖8為本發明節點脫離群首處理流程圖，具體為步驟D1、節點運動引起的網絡拓撲變化使成員節點與其群首相距兩跳或兩跳以上；步驟D2、所述成員節點監聽其他群所用的信道；步驟D3、成員節點判斷是否存在群首與之相鄰，是則執行步驟D4，否則返回執行步驟D2；步驟D4、成員節點根據監聽結果加入到具有最大選擇權值的群首所在的群中，成為該群的新成員節點；步驟D5、所述新成員節點向原群首發送加入新群消息；步驟D6、原群首從其成員列表中刪除該成員節點。
如果一個普通成員節點與它的群首相距兩跳以上(包括兩跳)，那麼它會監聽其他群所用的信道，如果發現有群首與自己相鄰(如存在相距一跳的新群首)，該節點會基於監聽到的群首的選擇權值選擇加入到一個群。加入新群之後，該節點會通過原群中的相鄰普通成員節點作為中繼節點通知原群首，然後原群首將會將其從自己的成員列表中刪除。如果監聽結果沒有發現符合要求的群首存在，該節點會通過中繼節點繼續與原群首保持聯繫，並繼續監聽其他群所用的信道，直至發現符合要求的群首並加入到新群。
實施例七本實施例是在實施例二技術方案基礎上，步驟33中調用相應處理程序進行分群結構更新包括成員節點失效處理。圖9為本發明成員節點失效處理流程圖，具體為步驟E1、節點運動引起的網絡拓撲變化使群首在一段時間內未收到成員節點消息；步驟E2、群首向成員節點發送詢問消息；步驟E3、群首判斷是否收到成員節點返回的確認消息，收到時執行步驟E4，否則將詢問計數值加1，執行步驟E5；步驟E4、保持原分群結構不變，節點失效處理完畢；步驟E5、群首判斷詢問計數值是否超過詢問計數閾值，是則執行步驟E6，否則返回執行步驟E2；步驟E6、群首從成員列表刪除該成員節點，節點失效處理完畢。
當有節點失效導致非正常狀態下離開網絡時，如果群首在一段時間內沒有收到來自該節點的數據或者是在向該節點發包後沒有收到確認信息，群首會發送一個詢問消息到該節點。如果該節點依然存在，它會發送確認信息給群首。否則，在嘗試多次發送詢問信息後群首依然沒有收到回復的確認信息，則群首認為該節點已經消失，並將它從自己的成員列表中刪除。
實施例八本實施例的技術方案是在圖1～圖9所示技術方案基礎上，增加了對網絡進行初始化分群的步驟。圖10為本發明初始化分群流程圖，具體為步驟1、網絡中所有節點廣播消息，所述消息包含節點ID和剩餘能量值；步驟2、每個節點根據收到消息生成一個鄰居節點表；
步驟3、每個節點判斷其剩餘能量值是否大於能量閾值，是則執行步驟4，否則執行步驟6；步驟4、所述節點判斷其節點ID是否在鄰居範圍未分群節點中為最小，是則執行步驟5，否則執行步驟7；步驟5、所述節點發送群首消息，宣布建立新群，所述新群ID為該節點的ID，初始化分群完畢；步驟6、所述節點等待，直至收到來自鄰居節點的群首消息，節點加入該群成為成員節點，初始化分群完畢；步驟7、所述節點判斷是否在一設定時間內收到來自鄰居節點的群首消息，收到時執行步驟8，否則返回執行步驟4；步驟8、節點加入該群成為成員節點，初始化分群完畢。
本實施例技術方案實際上是一種節能初始化分群方法，方法中的群首節點選舉是基於節點ID和剩餘能量值P，即當節點的剩餘能量值P大於能量閾值Pthreshold時，並且其節點ID在其鄰居範圍內是最小的，那麼該節點將被選舉為群首節點，其鄰居節點都加入到其中成為成員節點。具體地說，首先，網絡中所有節點廣播包含節點ID和剩餘能量值P的消息，通過這一輪廣播每個節點都可以知道自己的鄰居節點狀況，每一個節點建立一個鄰居節點表。在初始狀態下，所有節點的選擇權值W都設置為-1。如果節點的剩餘能量值P小於能量閾值Pthreshold，說明該節點不具備成為群首的基本條件，最終一定會接收到來自鄰居節點的群首消息，節點加入該群成為成員節點；如果節點的剩餘能量值P大於能量閾值Pthreshold，並且在其鄰居範圍內未分群節點中具有最小ID，該節點將會發送群首消息宣布建立新群，群ID為該節點的ID。如果節點發現自身節點ID並不是最小，它將面臨要麼加入到其他群，要麼等待一段時間直到其自身節點ID在鄰居範圍內最小，建立新群。
本實施例提供的節能初始化分群方法中，每個節點只需要發送兩輪控制消息便可以快速形成分群結構，方法執行完以後，所有節點都能夠最終決定自己的角色，因此可以獲得一個覆蓋全網的初始分群結構。與現有相關分群方法相比，本發明節能初始化分群方法的群首節點選舉不僅考慮了節點ID，還包括剩餘能量值P，而且將剩餘能量值P作為衡量是否具備成為群首的先決條件。這樣一來，本發明不僅具有僅需兩輪控制消息的交換即可建立分群結構，具有分群速度較快、分群保持過程簡單等優點，而且由於在群首選舉階段考慮了節點的剩餘能量狀態，避免了某些剩餘能量低的節點擔當群首以及部分節點長期擔當群首的可能性，確保了節點擔當群首的公平性，從而均衡了能量消耗，作為群首的節點不會因為能量消耗大使分群結構的穩定性在短時間內變差，因此消除了現有技術群分解和重構頻率加大、網絡性能惡化等技術缺陷。由於在群首選舉階段考慮了節點的剩餘能量狀態，確保了節點擔當群首的公平性，從而均衡了能量消耗，達到延長網絡整體壽命的作用。
本實施例流程簡單描述為採用節能初始化分群方法進行初始化分群，直到所有節點都能夠最終決定自己的角色，最終獲得一個覆蓋全網的初始分群結構；之後，穩定節能分群維護方法採用定期輪詢方式監視網絡中節點的狀態以維護分群結構。當處於輪詢狀態時，執行穩定節能分群維護方法，形成新的分群結構或維持原分群結構；在相鄰兩次輪詢之間，網絡拓撲進行自動監視，對分群結構變化進行探測，如果出現分群結構變化，可根據不同事件類型調用相應處理程序進行分群結構更新。上述實時監視和定期維護過程可在高速移動環境下有效保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡整體壽命。上述節能初始化分群方法和穩定節能分群維護方法的具體處理過程已在前面詳細介紹，這裡不再贅述。
最後所應說明的是，以上實施例僅用以說明本發明的技術方案而非限制，儘管參照較佳實施例對本發明進行了詳細說明，本領域的普通技術人員應當理解，可以對本發明的技術方案進行修改或者等同替換，而不脫離本發明技術方案的精神和範圍。
權利要求
1.一種穩定節能分群方法，其中，包括步驟步驟10、設定群首輪詢時鐘；步驟20、啟動輪詢時鐘；步驟30、判斷輪詢時鐘是否超時，超時時執行步驟40，未超時則執行步驟30；步驟40、群首輪詢群內成員節點，獲取成員節點的相對移動性值、相對剩餘能量狀況值和局部節點度值，計算各成員節點的選擇權值；步驟50、群首判斷其選擇權值是否低於選擇閾值，是則執行步驟60，否則執行步驟70；步驟60、群首激活群內候選節點，候選節點發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成；步驟70、群首選擇候選節點，候選節點監視群首狀態，執行步驟20。
2.如權利要求1所述的穩定節能分群方法，其中，所述步驟40中節點的選擇權值為Wi＝w1Si+w2Pi+w3Ri，式中，i表示節點ID，Wi表示節點i的選擇權值，Si表示節點i相對於其鄰居節點的相對移動性值，Pi表示節點i的相對剩餘能量狀況值，Ri表示節點i的局部節點度值，係數w1，w2和w3是相應參數的權重值，且∑wi＝1。
3.如權利要求1所述的穩定節能分群方法，其中，所述步驟70具體為步驟71、群首選擇具有最大選擇權值的成員節點為候選節點；步驟72、群首廣播發布消息，公布候選節點ID和各成員節點選擇權值；步驟73、候選節點定期檢查是否收到群首節點廣播的周期性消息，收到時執行步驟20，未收到時執行步驟74；步驟74、候選節點向群首發送詢問消息；步驟75、候選節點判斷是否收到群首返回的確認消息，收到時執行步驟20，否則執行步驟76；步驟76、候選節點判斷詢問計數值是否超過詢問計數閾值，是則執行步驟77，否則將詢問計數值加1後執行步驟74；步驟77、候選節點自動激活，發送群首消息，宣布成為新群首，其他成員節點和原群首加入新群，新的分群結構形成，返回執行步驟20。
4.如權利要求1或3所述的穩定節能分群方法，其中，所述步驟30中，當判斷輪詢時鐘未超時時，執行步驟步驟31、網絡拓撲自動監視，探測分群結構變化；步驟32、判斷分群結構是否變化，當分群結構變化時執行步驟33，否則執行步驟30；步驟33、根據不同事件類型，調用相應處理程序進行分群結構更新，更新結束後執行步驟30。
5.如權利要求4所述的穩定節能分群方法，其中，所述步驟33中調用相應處理程序進行分群結構更新包括節點加入處理，具體為步驟A1、新節點加入到網絡中；步驟A2、新節點交替監聽網絡中的所有信道；步驟A3、新節點根據監聽結果加入到具有最大選擇權值的群首所在的群中，成為該群的成員節點。
6.如權利要求4所述的穩定節能分群方法，其中，所述步驟33中調用相應處理程序進行分群結構更新包括節點退出處理，具體為步驟B1、退出節點向群首節點發送退網請求；步驟B2、群首節點向該退出節點發送一個離開確認信息，並從其成員列表中刪除所述退出節點；步驟B3、退出節點收到群首回復的離開確認信息後，正常離開網絡。
7.如權利要求4所述的穩定節能分群方法，其中，所述步驟33中調用相應處理程序進行分群結構更新包括群首相遇處理，具體為步驟C1、節點運動引起的網絡拓撲變化使兩個群首相遇；步驟C2、判斷一個群首是否可以包含另一群首及其成員節點，是則執行步驟C3，否則執行步驟C4；步驟C3、兩個群合併，形成新群；步驟C4、分群結構保持不變。
8.如權利要求4所述的穩定節能分群方法，其中，所述步驟33中調用相應處理程序進行分群結構更新包括成員節點脫離群首處理，具體為步驟D1、節點運動引起的網絡拓撲變化使成員節點與其群首相距兩跳或兩跳以上；步驟D2、所述成員節點監聽其他群所用的信道；步驟D3、成員節點判斷是否存在群首與之相鄰，是則執行步驟D4，否則返回執行步驟D2；步驟D4、成員節點根據監聽結果加入到具有最大選擇權值的群首所在的群中，成為該群的新成員節點；步驟D5、所述新成員節點向原群首發送加入新群消息；步驟D6、原群首從其成員列表中刪除該成員節點，成員節點脫離群首處理完畢。
9.如權利要求4所述的穩定節能分群方法，其中，所述步驟33中調用相應處理程序進行分群結構更新包括成員節點失效處理，具體為步驟E1、節點運動引起的網絡拓撲變化使群首在一段時間內未收到成員節點消息；步驟E2、群首向成員節點發送詢問消息；步驟E3、群首判斷是否收到成員節點返回的確認消息，收到時執行步驟E4，否則將詢問計數值加1，執行步驟E5；步驟E4、保持原分群結構不變，節點失效處理完畢；步驟E5、群首判斷詢問計數值是否超過詢問計數閾值，是則執行步驟E6，否則返回執行步驟E2；步驟E6、群首從成員列表刪除該成員節點，節點失效處理完畢。
10.如權利要求1～9任一所述的穩定節能分群方法，其中，還包括對網絡進行初始化分群的步驟，具體為步驟1、網絡中所有節點廣播消息，所述消息包含節點ID和剩餘能量值；步驟2、每個節點根據收到消息生成一個鄰居節點表；步驟3、每個節點判斷其剩餘能量值是否大於能量閾值，是則執行步驟4，否則執行步驟6；步驟4、所述節點判斷其節點ID是否在鄰居範圍未分群節點中為最小，是則執行步驟5，否則執行步驟7；步驟5、所述節點發送群首消息，宣布建立新群，所述新群ID為該節點的ID，穩定節能分群完畢；步驟6、所述節點等待，直至收到來自鄰居節點的群首消息，節點加入該群成為成員節點，穩定節能分群完畢；步驟7、所述節點判斷是否在一設定時間內收到來自鄰居節點的群首消息，收到時執行步驟8，否則返回執行步驟4；步驟8、節點加入該群成為成員節點，穩定節能分群完畢。
全文摘要
本發明涉及一種穩定節能分群方法，包括步驟設定群首輪詢時鐘；群首輪詢群內成員節點，獲取成員節點的相對移動性值、相對剩餘能量狀況值和局部節點度值，計算各成員節點的選擇權值；群首判斷其選擇權值是否低於選擇閾值，是則群首激活群內候選節點，候選節點發送群首消息，宣布成為新群首，新的分群結構形成，否則原群首保持群首角色不變；群首選擇具有最大選擇權值的成員節點為候選節點。本發明針對節點移動性對分群結構穩定性的劇烈影響，通過定期輪詢方式監視網絡中節點的狀態，根據網絡拓撲變化，及時實現對分群結構的維護，有效保證分群結構的穩定性，同時確保節點擔當群首的公平性，從而均衡能量消耗，延長網絡的整體壽命。
文檔編號H04L29/06GK1921436SQ20061009944
公開日2007年2月28日 申請日期2006年7月20日 優先權日2006年7月20日
發明者劉凱, 張軍, 宋學貴 申請人:北京航空航天大學