[發明專利]基于正六邊形網格劃分的改進非均勻分簇算法

有效

• 申請號: 201711146402.2
• 申請日: 2017-11-17
• 公開（公告）號: CN107820257B
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 康琳;宋仁旺;董增壽;盧龍
• 申請（專利權）人: 太原科技大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W52/02;H04W40/10;H04W40/04
• 代理公司: 北京國坤專利代理事務所(普通合伙) 11491
• 代理人: 趙紅霞

本發明基于正六邊形網格劃分的改進非均勻分簇算法屬于網絡節點算法領域，解決了現階段無線傳感器網絡規模趨于擴大化和網絡節點部署密集易造成數據冗余、能耗較大等問題，提出基于正六邊形網格的無線傳感器網絡非均勻分簇算法(HGUC)，算法首先將感知區域進行正六邊形網格劃分，其次，在簇頭選舉階段，選舉每個網格中能量最大的節點作為備選簇頭節點，最終簇頭節點的選取考慮最優簇頭數、節點的剩余能量、每個網格內存活節點個數等因素；在成簇階段，根據簇首與基站的距離、節點剩余能量等因素，設定簇群范圍的大小，從而降低數據冗余，實現網絡能耗均衡。

技術領域

本發明屬于網絡節點算法領域，特別是涉及一種基于正六邊形網格劃分的改進非均勻分簇算法。

背景技術

無線傳感器網絡是一種面向應用的網絡，被廣泛應用于軍事監控、農業和醫療健康的監測與監護等領域。其節點布置密集和數據采集的周期性，易形成大量冗余數據，極大地消耗了節點有限的能量。目前，常用的節能方法是路由節點在數據轉發之前進行數據融合處理，使有效數據得到最大程度壓縮，從而降低冗余。

現階段常用的節能方法是路由簇頭節點在數據轉發之前進行數據融合處理，使有效數據得到最大程度壓縮，從而降低冗余，但此方法沒有從源頭數據采集階段減少冗余數據采集，數據融合處理能耗較大，

LEACH是經典的分簇路由算法，與傳統的靜態路由比較，更適合現階段大規模、實時性要求高的網絡，可以有效延長網絡生存周期，但LEACH協議存在的缺陷是簇頭選舉時未能考慮節點的剩余能量和節點能耗均衡，單跳通信易造成“熱區”。

EEUC(Energy Efficient Uneven Clustering)作為一種有效的非均勻分簇路由算法，解決了LEACH協議帶來的“熱區”問題，即，通過簇間多跳模式進行數據傳輸，利用節點競爭半徑使得離基站越遠的簇的范圍越大，從而節約簇內能量用于簇間使用，但算法簇頭選舉頻繁、確定簇競爭半徑時沒有考慮節點剩余能量等問題，節點能耗較大，大大降低了網絡生存周期。

翟春杰在基于分區的能耗均衡路由協議主要通過網絡分區,提出使得距離基站遠近不同的分區內簇個數不同來均衡簇間與簇內能耗，但是該算法沒有考慮節點密度，節點密集區域簇頭數量較少，加速了個別節點死亡速率，另外還有采用權值局部競選簇頭,簇頭通過距離數值等構建半徑不等的多個簇。

另外有的算法中采用網絡正方形網格劃分，感知區域節點覆蓋重疊面積較大，數據冗余較多。針對以上算法綜合問題，本文提出一種基于正六邊形網格劃分的改進非均勻分簇算法，旨在從根本上減少節點冗余數據的采集，簇頭節點的選舉考慮網格區域節點密度、節點剩余能量、減少簇頭選舉輪數等多個因素，最大程度的減少節點數據采集傳輸能耗，顯著地延長了網絡生存壽命。

發明內容

本發明克服現有技術存在的不足，解決了現階段無線傳感器網絡規模趨于擴大化和網絡節點部署密集易造成數據冗余、能耗較大等問題，旨在提供一種基于正六邊形網格劃分的改進非均勻分簇算法，算法采用虛擬正六邊形網格劃分，在每個網格中選出能量最大的節點作為備選簇首節點，休眠網格冗余節點，減少了網格內活躍節點的個數，以降低網絡冗余數據采集和傳輸干擾，并減少不必要的數據監聽；在成簇階段，根據備選簇首節點與基站的距離和備選節點當前網格內鄰居節點數目、剩余能量，改進簇首節點競爭半徑來構造大小不等的簇，進而平衡簇內及簇間能耗，有效的延長網絡的生存周期。

為解決上述技術問題，本發明采用的技術方案為：

基于正六邊形網格劃分的改進非均勻分簇算法，本算法按照以下步驟進行：

1)簇建立階段：以虛擬正六邊形網格劃分，在每個網格選舉能量最大的節點作為備選簇頭節點，同時考慮每個網格內存活相鄰節點數，確保網格存活節點中最終選出能量最大且具有最多相鄰節點數的節點成為最后的簇頭節點，具體算法如下：

首先，確定網格最優簇頭節點個數，最優簇頭數表示如式(5)