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

有效

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

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

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

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

式(5)中，n為網絡節點個數，A為監測區域邊長，ε_fs、ε_amp分別為傳感器節點中放大電路在自由空間和多徑衰落模式下的能耗系數，L_BS為sink點與監測區域中心點距離；

然后，根據最優簇頭數K_opt、備選簇頭節點剩余能量以及網格內節點密度，以P概率在備選簇頭中選出部分節點作為最終簇首，首先每個備選簇頭隨機生成一個大小在0到1之間的數值，若該數值小于閾值則當選簇頭，具體閾值公式如下：

D表示在最后1/p輪中沒有當選過簇頭節點的集合，E_r(i)表示第r輪備選簇頭節點當前的能量，表示第r輪備選簇頭所在網格f的節點的平均能量，w(f)表示網格f的節點數量，α為權重系數，取值為0～1；

2)成簇階段：根據備選簇頭節點與基站的距離和備選節點當前網格內節點密度、節點剩余能量計算簇頭節點競爭半徑來構造大小不等的簇；簇頭的競爭半徑計算公式如下：

式(7)中：d_max和d_min分別表示網絡中簇頭節點到基站的最大和最小距離，R₀為所有節點在網絡初始化時的半徑，E₀、E_r(i)分別表示節點的初始能量和第r輪簇頭節點i的當前能量，d(i,sink)表示節點i到sink節點的距離，c被定義為半徑控制因子，其取值范圍為c∈(0,1)；

3)數據傳輸階段：簇間采用多跳的數據傳輸模式，進而平衡簇內及簇間能耗，有效的延長網絡的生存周期。

2.根據權利要求1所述的基于正六邊形網格劃分的改進非均勻分簇算法，其特征在于：所述正六邊形網格劃分的具體方法如下：

1)在保證節點圓形覆蓋的情況下，將兩兩圓重疊的區域進行簡化，利用直線段代替圓的重疊區域，得到圓的內接正六邊形；

2)確定區域的劃分：以某一個正方形的中心點作為坐標原點，任意兩個相鄰的網格內節點最大監測距離大小與節點監測半徑d和正六邊形邊長r關系如式(1)所示，建立直角坐標系，確定第一個網格位置，以此為原點將監測區域劃分為若干個正六邊形虛擬網格；

3)確定網格編號：作長為2m寬為2n的矩形，其中，正六邊形邊長設為L，m和n分別為單位坐標長度，各個網格的中心點(x₀,y₀)所屬的網格編號為

確定每個節點(x_i,y_i)所屬網格編號C_ID(i)。

3.根據權利要求2所述的基于正六邊形網格劃分的改進非均勻分簇算法，其特征在于：所述節點所屬網格編號的確定方法如下：

1)設節點坐標為(x_i,y_i)，六邊形的邊長為：l，橫坐標水平兩個六邊形的中心的距離為2n，

則縱坐標垂直兩個六邊形的中心距離為2m，則

求出：

(1)橫坐標除n取整：k(i)＝X(i)/n (a)

(2)縱坐標除m取整：z(i)＝Y(i)/m (b)

(3)橫坐標除了整的n的剩余：a(i)＝X(i)-k(i)×n (c)

(4)縱坐標除了整的m的剩余：b(i)＝Y(i)-z(i)×m (d)

求余數的作用：運用a(i)²+b(i)²≤(m-a(i))²+(n-b(i))² (e)

判斷節點在此六邊形中還是在右斜對角六邊形中；

2)判斷

(1)當k(i)與z(i)均為偶數，且(e)式成立時，節點所在的網格編號為：C_ID(i)＝4×k(i)+z(i)+1 (f)

(2)當k(i)與z(i)均為奇數，且(e)式成立時，節點所在的網格編號為：C_ID(i)＝4×(k(i)-1)+z(i)+1 (g)

(3)當k(i)與z(i)均為偶數，且(e)式不成立時，節點所在的網格編號為：C_ID(i)＝4×k(i)+z(i)+2 (h)

(4)當k(i)與z(i)均為奇數，且式(e)不成立時，節點所在的網格編號為：C_ID(i)＝4×(k(i)+1)+z(i)+2 (i)

(5)當(a)式為偶數，(b)式為奇數，(e)式成立，節點所在的網格編號為：C_ID(i)＝4×k(i)+z(i)+2 (g)

(6)當(a)式為偶數，(b)式為奇數，(e)式不成立，節點所在的網絡編號為：C_ID(i)＝4×k(i)+z(i)+1 (k)

(7)當(a)式為奇數，(b)式為偶數，(e)式成立，節點所在的網格編號為：C_ID(i)＝4×(k(i)-1)+z(i)+2 (l)

(8)當(a)式為奇數，(b)式為偶數，(e)式不成立，節點所在的網絡編號為：C_ID(i)＝4×(k(i)+1)+z(i)+1 (m)。