上下文相關的非均勻分簇路由算法的製作方法
2023-11-09 01:04:37 1
專利名稱：上下文相關的非均勻分簇路由算法的製作方法
技術領域：
本發明涉及一種非均勻分簇路由算法，尤其涉及一種上下文相關的非均勻分簇路
由算法。
背景技術：
近幾年國際上對「物聯網」的高度關注，「物聯網」被譽為繼計算機和網際網路之後的第三次信息技術革命，成為未來科學的制高點。掀起了研究和應用的熱潮，2006年，我國把WSN作為重大專項、優先發展主題、前沿領域被列入《國家中長期科學與技術發展規劃(2006-2020)》。2009年美國將物聯網和新能源列為振興經濟的兩大重點，並首次提出「智慧地球」這一理念，同年中國提出「感知中國」，並將物聯網正式列為國家五大新興戰略性產業之一，並寫入「政府工作報告」，引起全社會的極大關注。和傳統的網際網路相比，物聯網具有廣泛應用的感知技術、建立在網際網路上的泛在網絡、智能處理和實時控制等鮮明的特徵。其目的是實現物與物、物與人，所有的物品和網絡的互連，方便識別、管理和控制。而無線傳感器網絡既是「物聯網」的高級應用，又是其中不可或缺的關鍵技術。無線傳感器網絡(WSN)綜合了傳感器技術、微電子技術、嵌入式技術、無線通信技術和分布式信息處理技術，能夠協同地實時監控、感知和採集被監測對象的信息，通過數據融合和處理後，傳送給需要這些信息的用戶，從而實現遠程實時監控。無線傳感器網絡具有以下特點:有限的節點能量、無線自組織網絡、低功耗低成本部署、以數據為中心和應用相關性。因此，針對不同的應用需求，開發相應的通信協議成為了當前研究的熱點和難點。利用現有能源延長網絡的生命周期是無線傳感器網絡關鍵技術之一。將節點組織成簇的形式可以有效地減少網絡的能耗。分簇算法是無線傳感器網絡中實施分層路由所採用的重要方法。WCA是針對Ad Hoc網絡提出了一種考慮多種因素組合的加權分簇算法。但該算法針對AD Hoc網絡，選取參數比較困難。在無線傳感器網絡的分簇算法中，最具代表性的是低功耗自適應分簇路由協議(LEACH)。儘管它與一般的平面多跳路由協議相比，可以將網絡生命周期延長15%，但是，期望的網絡簇頭佔所有節點的比例決定了每輪分簇數目。在實際應用中，該最佳比例的確定是十分困難的，這與網絡規模和節點密度有關，通常取固定數5%或10%。在HEED分簇算法中，簇頭的選擇主要依據主、次兩個參數,主參數是剩餘能量，具有較多能量的節點以較大的概率成為簇頭；次參數是簇內通信代價。實驗表明，HEED的分簇速度快，能產生分布基本均勻的簇頭和合理的網絡拓撲。但該算法各節點能耗不均衡，路由策略能量不夠優化。由於無線網絡中分層路由的特點，靠近基站的節點會承擔更多的數據傳輸，因此，能量消耗更快，從而導致靠近基站的區域的節點死亡的更快，我們成這個現象為能量空洞。針對這個現象分均勻分簇路由算法(EEUCR)提出了一種基於競爭半徑的分簇策略，緩解了這一現象。但是EEUCR的分簇算法仍然使用隨機選擇的方法，沒有考慮局部信息，這使得分簇效率不夠優化。其路由算法使用的探測回應模式，這明顯不是一種穩定高效的路由算法。
因此需要一種既可以平衡網絡能量消耗又可以延長網絡生存時間的分簇路由算法來解決上述的問題。發明名稱:基於不均勻分簇的無線傳感器網絡拓撲控制方法，申請號:200810035214,該專利的分簇階段，雖然使用了非均勻分簇，具體信息交換細節專利沒有說明，並且選取蔟頭是僅僅根據位置而非參照能量；路由階段，使用反向路由，發送探測幀發現路由，這樣做不能確定有效的廣播距離，也不能確定發送這個信息以後沒有響應，該專利中所公開的的路由協議的穩定性是不夠的。並且這個算法對於能量空洞問題只做了分均勻分簇處理，路由方面沒有做處理，所以對於靠近基站的蔟頭能量消耗是非常快的，並且，蔟頭的更換隻是按照位置信息，這樣能量均衡是不夠的，不能保證整個路由的連通性。發明名稱:一種無線傳感器網絡路由方法，申請號:200910039496，該專利中:
1.分簇的時候產生隨機數與閾值T比較來決定是否成為蔟頭，但是蔟頭的形成是完全隨機的，因此分簇方法存在弊端，不能將能量和位置等信息綜合起來考慮；2.路由算法明顯的能量消耗不均勻，，所有的到基站的數據都要經過主蔟頭，並且只是使用這一個標準，重複的使用一條鏈路，很容易造成部分節點的過早死亡，而且還需要試探能量消耗。發明名稱:一種高能效的無線傳感器網絡非均勻分簇路由方法，申請號:201110131502，該專利中的分簇算法沒有考慮嵌入式節點受限的能量和資源，使用該分簇算法，分簇的信息沒有得到充分的利用，而是在路由時又一次發送廣播信息，而且如果要達到這麼複雜的控制邏輯，需要大量的信息統計和節點計算，這些無疑都需要大量的能量消耗。該申請的協議只關心模擬結果，沒有在複雜度和能耗之間找到一個平衡點，而且這個專利中的複雜邏輯控制，在實際情況中是跑不通的。
發明內容
本發明的目的就是為了解決上述問題，提供一種上下文相關的非均勻分簇路由算法，它具有實現簡單高效，有效節省能量，延長網絡生存時間，節省人力財力的優點。為了實現上述目的，本發明採用如下技術方案:一種上下文相關的非均勻分簇路由算法，包括分簇階段和路由階段，具體步驟為:步驟一:所有節點以Cltl為半徑廣播一次，Cltl為無線電能耗閾值；每個節點收到相應廣播信息以後，計算該節點權重以及對鄰居節點的投票值；每個節點廣播自己的投票值，鄰居節點收到投票值以後計算自己的最終得票；步驟二:如果節點的投票值是局部範圍內最大的，那麼節點選擇自己為簇頭，並且將自己的信息，包括自己的位置、剩餘能量、競爭半徑，通過控制幀以自己的競爭半徑廣播出去；步驟三:收到控制幀的節點若為簇頭，該簇頭將相應的信息加入到上級或者下級列表當中；若接收到控制巾貞的節點為普通節點，根據fitness函數和距離選擇最優的簇頭加入，並且發送退出選舉的信息給簇頭，包含了簇頭位置，剩餘能量以及競爭半徑；步驟四:收到退出選舉信息但是沒有入簇的節點，記錄收到的相應簇頭的信息，包括簇頭位置，剩餘能量，這些節點利用最後的鄰居節點投票值增加自己的節點權重，使得在下一輪的選舉中擁有更大的優先級成為簇頭；
步驟五:重複步驟一至步驟六，直至所有節點成為簇頭或者簇成員；步驟六:所有簇頭檢查自己是否擁有上級列表，如果上級列表為空，那麼就以η倍的競爭半徑廣播一次，η為大於I的實數；步驟七:與基站距離小於閾值DIS_DIRECTTO_BASE的簇頭直接與基站通信，將自己的check標誌置為1，到基站的跳數置為1，計算到基站的能量；然後從自己的下級列表中選擇一個最大的成員距離作為廣播半徑通過控制幀廣播一次，控制幀包含了簇頭的位置、剩餘能量、到基站需要的能量、到基站的跳數，閾值DIS_DIRECTTO_BASE為簇頭到基站的距離；步驟八:收到步驟九中的控制幀的簇頭檢查自己的狀態；步驟九:步驟十中的簇頭檢查自己的上級列表，如果所有的上級列表都已經發送過控制信息，那麼該簇頭設置自己的check標誌位1，並且廣播R0UTE_F0RM_MSG控制幀，若且唯若該蔟頭所有的上級列表都已經發送了 R0UTE_F0RM_MSG以後，簇頭修改自己的檢查位，然後發送R0UTE_F0RM_MSG控制幀，R0UTE_F0RM_MSG控制幀包括該簇頭的標識、該簇頭的位置、該簇頭的剩餘能量、該簇頭傳輸數據到基站所消耗的能量、該簇頭到基站所需要的跳數；步驟十:重複步驟八至步驟十一直至路由的時間段結束；步驟十一:如果簇頭到路由階段結束仍然沒有上級列表，那麼該簇頭直接與基站通信。所述步驟二中競爭半徑為:
權利要求
1.種上下文相關的非均勻分簇路由算法，包括分簇階段和路由階段，其特徵是，具體步驟為: 步驟一:所有節點以Cltl為半徑廣播一次，Cltl為無線電能耗閾值；每個節點收到相應廣播信息以後，計算該節點權重以及對鄰居節點的投票值；每個節點廣播自己的投票值，鄰居節點收到投票值以後計算自己的最終得票； 步驟二:如果節點的投票值是局部範圍內最大的，那麼節點選擇自己為簇頭，並且將自己的信息，包括自己的位置、剩餘能量、競爭半徑，通過控制幀以自己的競爭半徑廣播出去; 步驟三:收到控制幀的節點若為簇頭，該簇頭將相應的信息加入到上級或者下級列表當中；若接收到控制巾貞的節點為普通節點，根據fitness函數和距離選擇最優的簇頭加入，並且發送退出選舉的信息給簇頭，包含了簇頭位置，剩餘能量以及競爭半徑； 步驟四:收到退出選舉信息但是沒有入簇的節點，記錄收到的相應簇頭的信息，包括簇頭位置，剩餘能量，這些節點利用最後的鄰居節點投票值增加自己的節點權重，使得在下一輪的選舉中擁有更大的優先級成為簇頭； 步驟五:重複步驟一至步驟六，直至所有節點成為簇頭或者簇成員； 步驟六:所有簇頭檢查自己是否擁有上級列表，如果上級列表為空，那麼就以η倍的競爭半徑廣播一次，η為大於I的實數； 步驟七:與基站距離小於閾值DIS_DIRECTTO_BASE的簇頭直接與基站通信，將自己的check標誌置為1，到基站的跳數置為1，計算到基站的能量；然後從自己的下級列表中選擇一個最大的成員距離作為廣播半徑通過控制幀廣播一次，控制幀包含了簇頭的位置、剩餘能量、到基站需要的能量、到基站的跳數，閾值DIS_DIRECTTO_BASE為簇頭到基站的距離； 步驟八:收到步驟九中的控制幀的簇頭檢查自己的狀態； 步驟九:步驟十中的簇頭檢查自己的上級列表，如果所有的上級列表都已經發送過控制信息，那麼該簇頭設置自己的check標誌位1，並且廣播ROUTE_FORM_MSG控制幀，若且唯若該蔟頭所有的上級列表都已經發送了 ROUTE_FORM_MSG以後，簇頭修改自己的檢查位，然後發送ROUTE_FORM_MSG控制幀，ROUTE_FORM_MSG控制幀包括該簇頭的標識、該簇頭的位置、該簇頭的剩餘能量、該簇頭傳輸數據到基站所消耗的能量、該簇頭到基站所需要的跳數； 步驟十:重複步驟八至步驟十一直至路由的時間段結束； 步驟十一:如果簇頭到路由階段結束仍然沒有上級列表，那麼該簇頭直接與基站通信。
2.權利要求1所述一種上下文相關的非均勻分簇路由算法，其特徵是，所述步驟一中節點權重的步驟為: (1-1)確定節點Vi投給其某一鄰居節點Vj的選票V (Vi, Vj),
3.權利要求1所述一種上下文相關的非均勻分簇路由算法，其特徵是，所述步驟二中競爭半為:
4.權利要求1所述一種上下文相關的非均勻分簇路由算法，其特徵是，所述步驟六中若簇頭檢查自己到自己的上級列表為空，那麼就以兩倍的競爭半徑廣播一次。
5.權利要求1所述一種上下文相關的非均勻分簇路由算法，其特徵是，所述步驟八的具體步驟為: (8-1)如果check為O並且這個幀的源節點是該簇頭的上級列表成員，那麼就更新相應的上級列表表項，剩餘能量為控制幀中的剩餘能量，到基站的跳數為控制幀中的跳數加1，到基站的能量為發送數據到源簇頭加上該控制幀中到基站需要的能量； (8-2)如果check為0，並且這個幀的源節點不在上級列表中，那麼創建一個表項；(8-3)如果check為1，直接忽略這個控制幀。
全文摘要
本發明公開了一種上下文相關的非均勻分簇算法，克服了傳統的分層路由模型將分簇與路由相互隔離的缺點，將分簇階段的信息應用於路由形成階段，極大的縮減了網絡的準備時間以及減小了網絡的能量消耗。本發明應用基於選票機制的分簇算法，優化了區域的能量消耗。使用分時反向的洪泛算法，大大節省了路由發現所消耗的能量。可以有效的應用於大規模的區域監控，並證實了其能量負載均衡，節點行為穩定，網絡生存時間更長。
文檔編號H04L12/721GK103095577SQ20131006282
公開日2013年5月8日 申請日期2013年2月27日 優先權日2013年2月27日
發明者賈智平, 鞠雷, 鄭龍鵬 申請人:山東大學