[發明專利]基于集群劃分的水下無線傳感器網絡覆蓋漏洞修復算法

有效

• 申請號: 201811523945.6
• 申請日: 2018-12-13
• 公開（公告）號: CN109640333B
• 公開（公告）日: 2021-08-31
• 發明（設計）人: 張文波;譚小波;張林叢;付立冬;魏宣任
• 申請（專利權）人: 沈陽理工大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W24/04;H04W52/02;H04W84/18
• 代理公司: 沈陽利泰專利商標代理有限公司 21209
• 代理人: 王東煜

1.基于集群劃分的水下無線傳感器網絡覆蓋漏洞修復算法，其特征在于以下步驟：

步驟1：運用三維密集網絡的拓撲模型，將整個三維空間劃分為多個相同的虛擬組成單元，保證每一個分割單元內都存在一個可以正常工作的傳感器節點，就可以確定整個傳感器網絡是高度覆蓋的；

步驟2：漏洞檢測，進行相關定義并通過建立分割單元和覆蓋矩陣之間的映射，尋找出現的某些分割單元內存在失效節點，假設集群中可能出現覆蓋漏洞，再依據漏洞邊緣節點感知半徑的關系和距離分割單元中心長度確定是否真的存在覆蓋漏洞；

步驟2.1：相關定義

定義1：覆蓋率C_r：傳感器網絡的覆蓋率是指傳感器節點感知范圍V₁,V₂,…,V_n的交集與監控區域體積V_A的比值，即

定義2：分割單元：目標三維區域A可以被分割為若干個相同的多面體P_olytope，則本發明中將立方體作為分割單元；

定義3：集群：立方體分割單元與其26個一級物理鄰接單元組成的立方體稱為集群；

定義4：節點編號ID₀：使用節點在監控區域的三維坐標系中的坐標(x,y,z)作為節點的編號，記為ID_o＝(x,y,z)；

定義5：分割單元編號ID₁：每一個分割單元設置一個唯一的身份標識號碼，即分割單元編號ID₁＝(i,j,k)，其中i代表分割單元所處的行數，j代表分割單元所處的列數，k代表分割單元所處的層數；所以每一個編號為(i,j,k)的分割立方體的坐標范圍為：

因此，節點可以通過ID₀得到所在分割單元的編號：

定義6：集群編號ID₂：每一個集群設置一個唯一的身份標識號碼，即集群編號ID₂＝(a,b,c)；則該集群的坐標范圍為：

因此，節點可以通過ID₀得到所在集群的編號：

定義7：節點等級R_ank：根據節點在分割單元內的位置信息劃分節點的級別，記為節點等級R_ank；

定義8：通信半徑r_c：傳感器節點的通信范圍與感知范圍相似；

定義11：節點等級R_ank：根據節點在分割單元內的位置信息劃分節點的級別，記為節點等級R_ank；

定義12：失效節點：那些因為能量耗盡、部件故障等因素而不能夠正常實現感知、采集、處理和傳輸等功能的傳感器節點被稱為失效節點；

定義13：覆蓋漏洞：因為存在了失效節點，因此在傳感器網絡的監控范圍內就產生了一個不能被任何一個傳感器節點所覆蓋的連續的三維區域；

定義14：漏洞邊緣節點：如果覆蓋漏洞的周圍存在著可以正常工作的傳感器節點，那么稱這些傳感器節點為漏洞邊緣節點；

定義15：覆蓋矩陣：將分割單元的三維排列映射為二維矩陣，用來記錄分割單元內是否存在正常工作的傳感器節點，從而得到網絡的覆蓋狀況，因此這個二維矩陣就被稱為覆蓋矩陣；

步驟2.2：建立覆蓋矩陣

首先，臨時控制節點建立一個n×m的全0矩陣，表示該集群內的每一個分割單元中都不存在正常工作的傳感器節點，隨后，當臨時控制節點接收到數據時，判斷發送該數據的節點來自于哪個分割單元，從而就可以認為該分割單元內存在可以正常工作的傳感器節點，然后就根據分割單元與矩陣的映射關系將覆蓋矩陣相應位置上的數據更改為1，最后，當矩陣由全0變為全1時就表示覆蓋矩陣建立完畢；

因此分割單元與矩陣的映射關系如下：已知分割單元編號ID₁＝(i,j,k)，那么就規定ID₁＝(1,1,1)的分割單元映射在覆蓋矩陣上的位置為n＝1且m＝1，即覆蓋矩陣的第1行第1列的位置；ID₁＝(2,2,2)的分割單元映射在覆蓋矩陣上的位置為n＝5且m＝2，即覆蓋矩陣的第5行第2列的位置；ID₁＝(3,3,3)的分割單元映射在覆蓋矩陣上的位置為n＝9且m＝3，即覆蓋矩陣的第9行第3列的位置，以此類推，最終，我們可以得到分割單元與矩陣的映射關系為：

步驟2.3：找到失效節點所在的分割單元

已知集群編號為ID₂＝(a,b,c)，假設在覆蓋矩陣中n＝n₀且m＝m₀處的數據為0，即在覆蓋矩陣第n₀行第m₀列的位置上的數據為0，我們就可以確定失效節點所在的分割單元編號為ID₁＝(i,j,k)，對應關系如下所示：

步驟2.4：確定漏洞邊緣節點

根據漏洞邊緣節點定義可知，在覆蓋漏洞周圍的正常工作的傳感器節點都可以稱為漏洞邊緣節點，而本算法是基于集群劃分的概念，所以我們就可以將失效節點所在的分割單元近似的看作為覆蓋漏洞，因此漏洞邊緣節點就可以看作是該分割單元的一級物理鄰接單元內可以正常工作的傳感器節點，但是，如果按照這種方式找尋漏洞邊緣節點就很不合理，因為在此種情況下最多可能會出現26個漏洞邊緣節點，因此，根據集群的定義，我們就可以規定失效節點所在的分割單元的一級物理鄰接單元內的1類鄰接單元中可以正常工作的傳感器節點為該覆蓋漏洞的漏洞邊緣節點，即與該分割單元的一個面重合的鄰接單元內的正常工作的傳感器節點可以稱為漏洞邊緣節點；

步驟2.5：確定是否需要修復覆蓋漏洞

假設失效節點所在分割單元的編號為ID₁＝(i,j,k)，因此該分割單元中心位置點C的坐標為其中l表示分割單元邊長，在上一步驟中我們已經確定了漏洞邊緣節點，因此可以依次求得漏洞邊緣節點N_i與點C的距離為

如果存在d(N_i,C)≤r_s，則該覆蓋漏洞可以忽略不計，即不需要進行后續的漏洞修復操作，其中r_s表示該漏洞邊緣節點的感知半徑；否則需繼續執行漏洞修復算法；

步驟3：選擇關鍵位置，考慮傳感器節點的能量消耗問題，將傳感器節點所在位置分等級設置不同感知半徑，每個等級設置關鍵位置放置節點，使得完全覆蓋該節點所在分割單元；

由于考慮到傳感器節點的能量消耗問題，所以根據傳感器節點所在的位置將其分為三個等級，從而設置不同的感知半徑，因此將分隔單元的中心橫截面被分為三個等級，為每一個等級設置相應的關鍵位置，使得布放在該位置上的傳感器節點可以完全覆蓋該節點所在的分隔單元，由于可能會出現一個等級中存在多個關鍵位置的情況，因此，在本算法中就為每一個等級在滿足了關鍵位置定義的位置坐標中選擇一部分作為該等級的關鍵位置，所以，關鍵位置可以總結為：

(1)一級節點即R_ank＝1的節點所對應的關鍵位置為K₁₁，其位置坐標為：

(2)二級節點即R_ank＝2的節點所對應的關鍵位置分別為K₂₁、K₂₂、K₂₃、K₂₄，其位置坐標分別為：

(3)三級節點即R_ank＝3的節點所對應的關鍵位置分別為K₃₁、K₃₂，其位置坐標分別為：

步驟4：選擇補充節點，為了得到一個覆蓋率高且能耗均衡的傳感器網絡，出現覆蓋漏洞時，在冗余節點中喚醒剩余能量高且高覆蓋傳感器節點修復出現的漏洞，通過位置和剩余能量參數確定補充節點；

選擇的補充節點在考慮剩余能量的同時應該盡可能接近關鍵位置，因此設置位置系數用來表示傳感器節點與關鍵位置的遠近關系，距離關鍵位置越近的節點位置系數越大，假設傳感器節點Q的位置坐標為(x₀,y₀,z₀)，關鍵位置K的位置坐標為(x,y,z)，因此節點Q的位置系數為：

但是我們知道，關鍵位置不止一個，且與節點的等級有關，所以我們可以為不同級別的節點設置不同的位置系數；

(1)假設存在一個R_ank＝1的一級節點Q₁，其位置坐標為(x₁,y₂,z₃)，而一級節點所對應的關鍵位置K₁₁的位置坐標為(x,y,z)，則Q₁的位置系數為：

(2)假設存在一個R_ank＝2的二級節點Q₂，而二級節點所對應的關鍵位置分別為K₂₁、K₂₂、K₂₃、K₂₄，則Q₂的位置系數為：

(3)假設存在一個R_ank＝3的三級節點Q₃，而三級節點所對應的關鍵位置分別為K₃₁、K₃₂，則Q₃的位置系數為：

因此在選擇補充節點時就以位置系數與剩余能量E_residual為參考參數，選擇位置系數與剩余能量乘積最大的冗余節點作為補充節點，即最大的節點被選擇為補充節點，從而喚醒它來修復出現的覆蓋漏洞；

步驟5：根據確定好的關鍵信息，實現覆蓋漏洞修復算法；

步驟5.1：漏洞檢測，臨時控制節點根據漏洞檢測方法找到出現覆蓋漏洞的分割單元，確定分割單元編號ID₁＝(i₀，j₀，k₀)，首先臨時控制節點建立覆蓋矩陣，根據覆蓋矩陣找到可能出現覆蓋漏洞的分割單元；然后找到該覆蓋漏洞的漏洞邊緣節點；最后確定該覆蓋漏洞是否需要修復，如果需要修復，則繼續執行步驟5.2；否則，結束本算法；

步驟5.2：確定補充節點，臨時控制節點找到出現覆蓋漏洞的分割單元內的冗余節點，并根據位置系數與剩余能量的乘積進行排序，即按照計算式的結果從大到小排列該分割單元內的冗余節點，形成補充節點序列，位于序列首位的冗余節點稱為補充節點，其余的冗余節點稱為候選補充節點；

步驟5.3：喚醒補充節點，臨時控制節點按照此序列的順序喚醒冗余節點，如果臨時控制節點在的時間內收到了此節點發送的確認消息，即認為此補充節點喚醒成功，覆蓋漏洞修復完成，所以結束本算法；如果，臨時控制節點在的時間內沒有收到了此節點發送的確認消息，即認為該節點還處于深度休眠狀態，所以此補充節點喚醒失敗，繼續執行步驟5.4；

步驟5.4：繼續喚醒補充節點，喚醒補充節點失敗后，按照補充節點序列的順序依次喚醒后續的補充節點，直至臨時控制節點在的時間內收到候選補充節點發送的確認消息，此時認為喚醒成功，漏洞修復算法完成，所以結束本算法，如果臨時控制節點在補充節點序列遍歷完成后依舊沒有收到任何確認信息，則繼續執行步驟5.5，其中，l表示分割單元邊長，v表示聲信號在水下的傳播速率；

步驟5.5：找尋新的補充節點，當存在覆蓋漏洞的分割單元內找不到可以完成漏洞修復的補充節點后，需要找尋新的補充節點，因為在此水下無線傳感器網絡中，節點是可以豎直移動的，所以可以喚醒該分割單元豎直方向上傳感器節點，并將其移動到此分割單元內，從而實現漏洞的修復，根據出現覆蓋漏洞的分割單元的編號ID₁＝(i₀，j₀，k₀)，在此集群內找到分割單元編號為ID₁＝(i₀，j₀，k)的分割單元，并按照步驟5.2的方法，確定補充節點序列；

步驟5.6：喚醒新的補充節點，按照步驟5.3和步驟5.4的方法，喚醒新的補充節點，如果喚醒成功，則執行步驟5.7；否則，認為修復漏洞失敗，結束本算法，此時認為該網絡中節點數量有限，無法做到網絡的自愈，需要借助外界的幫助來完成漏洞的修復；

步驟5.7：移動被喚醒的節點，當節點被喚醒后，調節該節點與錨連接的繩長，使其移動到出現覆蓋漏洞的分割單元的中心橫截面內，假設存在覆蓋漏洞的分割單元編號為ID₁＝(i,j,k₁)，可以幫助修復該漏洞的補充節點所處的分割單元編號為ID₁＝(i,j,k₂)，如果k₁＞k₂，表示需要向上移動節點來修復存在的覆蓋漏洞，可以根據水下壓強公式P＝ρ·g·h來判斷是否到達了合適的位置，當傳感器節點所受壓強減小了(k₁-k₂)·g·ρ·l時，無需再向上移動，表示此時節點已經到達預定位置；如果k₁＜k₂，表示需要向下移動節點來修復存在的漏洞，當傳感器節點所受壓強增加了(k₂-k₁)·g·ρ·l時，無需再向下移動，表示此時節點已經到達預定位置，其中，ρ表示液體密度，g表示重力系數，h表示距離水面距離，l表示分割單元邊長。