[發明專利]一種基于置換搜索的無線傳感器網絡聚類分簇方法

有效

• 申請號: 202110060950.3
• 申請日: 2021-01-18
• 公開（公告）號: CN112911677B
• 公開（公告）日: 2022-08-26
• 發明（設計）人: 葉曉國;吳瑞
• 申請（專利權）人: 南京郵電大學
• 主分類號: H04W40/24
• 分類號: H04W40/24;H04W52/38;H04W84/18
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 王恒靜

1.一種基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，包括以下步驟：

(1)將某個區域中包含的多個傳感器節點劃分為若干個初始簇，并選出各個初始簇中的某個節點作為臨時簇首，此時設置軌跡表為空；

(2)計算各簇內各個節點的聚合度值以及和整個該區域的聚合度值；

各簇內各個節點的聚合度值表示為：

整個該區域的聚合度值表示為：

其中，K為在該區域內劃分的簇的總數，m為每個簇中包含的傳感器節點總數，1≤i≤K，1≤j≤m，α表示距離調節參數；β表示能量調節參數，α+β＝1，表示第i個簇中節點j與基站BS的曼哈頓距離；表示第i個簇中節點k到節點j的曼哈頓距離；表示第i個簇中節點j向基站BS傳輸單位數據量消耗的能量；表示第i個簇中節點j向節點k傳輸單位數據量消耗的能量；

(3)判斷各簇的當前臨時簇首的聚合度值是否為各簇內各個節點的聚合度值的最大值，若是，轉入步驟(5)，否則，轉入步驟(4)；

(4)選取各簇的最大聚合度值對應的節點為各簇的簇首，并將軌跡表中與已調整的各簇中非當前簇首相關的記錄清空，轉入步驟(5)；

(5)判斷是否達到終止條件，終止條件為達到最大的迭代次數或整個該區域的聚合度值穩定地收斂；若達到，轉入步驟(9)，否則，當前迭代次數加一后，轉入步驟(6)；

(6)將各簇中聚合度值中位數以下對應的節點選為待置換節點；

(7)按照置換規則進行置換，判斷是否置換成功，若置換成功，轉入步驟(8)，如果置換失敗，轉入步驟(6)；

(8)將置換成功的各簇中簇首與簇內節點信息錄入軌跡表，并轉入步驟(2)；

(9)輸出各簇最優簇首節點信息和各簇的節點信息，完成網絡中所有節點的分簇操作，得到最優的分簇結果，并輸出最終的分簇結果。

2.根據權利要求1所述的基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，所述軌跡表為由K個帶有各簇編號的空間組成，每個空間中均由鍵和值組成的鍵值對構成，鍵對應的是第i個簇的簇首信息，值對應的是一組鏈表，鏈表中存儲的是第i個簇中所有節點組成的對象信息。

3.根據權利要求1所述的基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，所述步驟(3)具體為：

根據各簇內節點的聚合度值DP_i^j值的大小，將最大的DP_i^j值所對應的節點j選舉為新一輪該簇的簇首節點即h_i＝max(DP_i^j)。

4.根據權利要求1所述的基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，所述步驟(7)中，置換規則具體為：

(71)計算各簇的待置換節點對各簇簇首的ξ值；

(72)選取各簇中對簇首的值低于該簇的待置換節點對應的ξ值的節點，若選取的數量小于該簇的待置換節點數，則該簇退出置換，否則，將選取的值按從小到大順序排列；

(73)各簇優先選取最小的值對應的節點作為待置換節點，若各簇待置換節點產生競爭關系，即：多個簇選取的待置換節點為同一個，其中，r表示簇a中最小ξ值對應的預選節點，n表示簇b中最小ξ值對應的預選節點，則將各簇中取值最小的節點作為置換節點，其余簇的待置換節點的選取依序順延，若該簇中滿足要求的值對應的節點數小于該簇的待置換節點數，則該簇退出置換；

(74)若至少有兩簇的節點滿足置換操作，則轉入步驟(75)，否則轉入步驟(6)；

(75)若軌跡表中不包含符合條件的待置換節點與對應簇其他節點組成的集合對象信息，則轉入步驟(8)，否則，轉入步驟(6)。

5.根據權利要求4所述的基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，各簇中對簇首的值，表示為：

其中，表示第i個簇的簇首節點距離基站的曼哈頓距離；表示第x個簇中待置換節點j距離第i個簇的簇首的曼哈頓距離；表示第i個簇的簇首向基站傳輸單位數據量消耗的能量；表示第x個簇中待置換節點j向第i個簇的簇首傳輸單位數據量消耗的能量。

6.根據權利要求4所述的基于置換搜索的無線傳感器網絡聚類分簇方法，其特征在于，所述步驟(7)中，置換失敗的情況還包括：各簇中聚合度值中位數以下的節點均參與置換且所有簇均置換失敗，則各簇除簇首外，所有節點均參與置換，按置換規則繼續置換，仍然置換失敗；此時置換失敗，但各個簇狀態穩定，此時的各簇簇首即是各簇的最優簇首，提前結束迭代，輸出各簇的最優簇首，轉入步驟(9)。