水下傳感器網絡自組織連通恢復仿真

趙高麗，宋軍平

(1.河南科技學院信息工程學院，河南 新鄉 453003；2.武漢理工大學信息工程學院，湖北 武漢 430070；3.河南科技學院新科學院，河南 新鄉 453003)

1 引言

水下傳感器網絡最引人注目的是可以在無人值守的水下嚴酷環境里工作、減少人力成本，同時提供一種完全自動化的數據收集系統，在水下傳感器網絡應用里，傳感器節點的處理能力是有限的，因此期望部署的傳感器組成了一種連通的網絡，在運行任務時，互相協作，把采集到的數據輸送至基站，因為傳感器節點的能量來源是電池供電設備，導致水下傳感器會受到能量耗盡導致設備停運的影響，并且，水下惡劣環境與惡意攻擊也容易使節點出現大規模損壞，在這些情況中，水下傳感器網絡的通信就容易斷開，數據的傳輸就會收到限制。對此國內外學者提出了以下解決方法。

文獻[1]使用拓撲分析法對傳感器檢測，確定受損區域，并更新主網絡拓撲參數，之后通過孤島方案提升DG的利用率同時恢復最大負荷量，最后將DG并網從而恢復傳感器網絡連通。但是該方法只是單純的通過檢測來判斷受損區域，并未對受損區域進行劃分，在恢復時這就需要對所有水下傳感器區域進行檢測，導致資源大量消耗。文獻[2]通過譜類算法對傳感器網絡的拓撲結構優化，進而縮短連通恢復的時間，之后構建恢復路徑與負荷恢復模型，再從連通性恢復時間、路徑非連通修正與不確定負荷恢復效率的角度，再次進行針對性優化，最后在融入電壓強約束從而完成對傳感器網絡連通的恢復。但是該方法并沒有精準的獲得受損壞的傳感器區域，這就導致了在最后完成連通恢復后，容易出現傳感器網絡遺留的問題。文獻[3]首先通過聯合稀疏分解方法，融合所有傳感器受損的信號，并進行分類，進而確定傳感器受損的區域，之后提取共通分量，利用信號分塊方法，減少起始稀疏度和步長所帶來的影響，最后將共通分量融入到受損的傳感器網絡節點內，進而恢復傳感器的連通性。但是該方法只是對網絡的連通性數據進行了恢復，并沒有對整體傳感器進行受損預防和實體恢復，導致后期傳感器網絡可能會出現二次受損。

上述問題中存在的資源消耗大、損毀檢測不精準與二次損壞問題，對此本文提出了一種水下傳感器網絡自組織連通恢復方法，通過MACRA算法和第二備用節點選擇夠有效的對傳感器網絡的自組織連通恢復，并且恢復的效率較高，不會出現大量的資源浪費情況。

2 水下傳感器網絡自組織連通恢復

2.1 水下傳感器網絡破壞分析

本文研究的是部署在水下環境內監控指定區域的傳感器，節點即靜態的，其感知半徑與通信半徑是不會出現變化的，傳感器節點只要位于通信半徑的范圍里就能夠互相通信，并把獲得的數據傳輸至基站內進行對應的處理，傳感器節點[4]可以使用相關的定位方法得到自身坐標信息，整體網絡使用分簇式層次拓撲結構。

通常情況下，傳感器節點有可能因為資源的消耗而失效，但一般狀態下只會導致少數的節點失效，如果不干擾網絡的連通，就能夠不做任何處理；反之也只是需要探測找出對應的失效節點，然后在重新放置節點即可。但在本文關注的水下環境里，除了能量消耗失效外，傳感器網絡節點也可能會受到水下環境的干擾，導致大規模失效，在此狀態下可能會出現整體網絡遭到破壞，具體場景如圖1所示。

圖1 水下傳感器網絡遭到破壞場景圖

在該狀態下，實現網絡連通[5]要求部署新的節點，不論是特定的用在通信的中繼節點，還是新部署和初始節點同樣的傳感器節點，增加節點同時對其進行部署都是需要大量成本的，所以通過最少的節點來完成網絡連通恢復是本文主要目的。把每一個新部署的節點叫做中繼節點，同時擬定這些節點在水下同為靜止不懂，并擁有相同的通信半徑R。傳感器網絡受到破壞后被劃分的獨立子網絡叫做分區。

在傳感器網絡劃分為多種獨立的分區后，節點經過互相通信就可以得到處理相同分區的其它節點[6]信息，同時選擇適合的代替節點，把分區擬定成代替節點的位置。網絡連通問題擬定成圖連通問題，同時擬定n種分區，然后通過網絡的全局分區信息，借助特定的巡視裝置把分區的信息輸送至基站。

2.2 分區搜索和代替節點確定

怎樣搜索獨立的分區和找到所有分區的代替傳感器節點，是在部署中繼節點之前就需要解決的兩種問題。對此，本文利用構造連通支配集方法建造出所有獨立分區的連通子樹[7]，通過所有沒被破壞的節點確定自身屬于的分區，同時了解分區的信息。對于每一個獨立的分區，本文取連通子樹里節點度最大的節點當做所有分區的代替節點，大致流程如下所示：

首先利用關聯分簇方法選擇節點，之后簇頭節點傳輸信息至其周圍的鄰居節點，通過一段時間收斂獲得所有鄰居節點的回復信息，憑借接收的回復信息取距離簇頭節點距離最長的鄰居節點當做支配節點。對應的支配節點繼續運行上述流程，直至確定所有獨立分區的支配集，從而形成多種連通子樹。最后取連通子樹立節點度最大的節點當做所有分區的代替節點，如果存在多種節點度同等的節點，就取ID最小的節點當做代替節點。

確定了所有分區的代替節點之后，把代替節點的坐標信息和節點的ID傳輸至分區里所有節點內，使得相同分區所有節點都儲存有代替節點的ID與坐標信息。

在巡視裝置對所部署監控區進行巡視采集時，巡視裝置只要接到分區里任意一種節點就能夠得到該分區的代替節點的ID與位置，最后把每一個分區代替節點信息傳輸至基站。

2.3 MACRA算法描述

本文提出的MACRA算法，即完成水下傳感器網絡的自組織連通恢復，使用多種節點在多種獨立分區之間進行移動，進而將連通恢復。MACRA算法擁有模糊連通恢復機制[8]與精確連通恢復機制兩個部分，這兩種部分的目標就是找出適合的水下傳感器節點和在分區之間定位合適的移動路線終點與起點位置。下面詳細描述MACRA的模糊連通恢復機制與精準連通恢復機制。

2.3.1 模糊連通恢復機制

模糊連通恢復首先通過網絡分割技術把整體水下傳感器網絡分割成多種具有一定規則的區域，并使用A1，A2，A3來代替，每種網絡點都歸屬至一種特定的區域Ak，區域的尺寸通過用戶的需求來擬定，在網絡里多種獨立分區組成后對所有分區進行所占區域的編號標記。如圖2所示，分區G1占A1與A2兩種區域。相較于隨機一種獨立分區需要選取一種中繼分區Gy來完成連通，基站sink能夠當做為一種獨立的中繼分區。

圖2 區域劃分

MACRA算法的模糊連通機制是以網絡區域當做估算單位，首先定位選擇連接的兩種分區Gx與Gy所占據的區域，對這兩種區域的確定需要在兩點要求之間進行權衡。這兩種要求為兩種區域長度盡量短與重新連接[9]方位應該符合現實輸送目的，即新的傳輸方位應該盡可能的偏向基站傳輸。用數學公式介紹就是選擇滿足模糊定位函數f1(Gx)最小值的兩種區域，函數f1(Gx)表示成

minf1(Gx)=αD(Ai，Aj)+βD(Aj，Ak)

(1)

式中D(Ai，Aj)代表Ai至Aj的歐式長度，D(Aj，Ak)代表Aj至Ak的歐式長度，此處通過區域的中心代替區域的坐標[10]，而α與β即常系數。如圖3所示，白色的點表示區域的中心位置，相較于獨立分區G3選取G2當做中繼分區，而Ai至Aj即水下傳感器節點的連接區域。

2.3.2 精準連通恢復機制

模糊定位函數在很大程度上減少了移動節點的選取范圍，只需要在大體定位的合適的傳感器節點進行輔助移動[11]至指定位置來恢復網絡的連通，精準連通恢復機制即同于完成這種目的，大致傳感器節點與移動位置的選擇綜合考慮尺寸與節點局部密度兩種因素。相較于隨機傳感器節點i，以該節點為中心的一種指定范圍的圓形區域里，部署的傳感器節點的總數量定義成該節點的局部密度，以σi來代替。選取節點的移動長度應該盡量縮短，這樣就能夠降低傳感器節點的移動質量要求，并且移動節點的終點與起點局部密度最好盡量擴大。如果某一種傳感器節點的局部密度變大，就證明節點對網絡連通性的干擾越小，因為在該節點遭到破壞導致失效后，能夠代替該節點的節點數越多，那么該節點對其鄰居們的數據傳輸的干擾越小，該節點對網絡的連通性干擾越小。

在運行模糊連通恢復機制之后，Ai與Aj兩種區域被擬定成水下移動傳感器節點移動的終點位置pi與起點位置pj所處的區域，精準定位函數f2(Gx)表示成

minf2(Gx)=μD(pi，pj)+φ/p(pi)

(2)

minf2(Gy)=μD(pi，pj)+φ/p(pj)

(3)

因此，水下傳感器節點的源與目的坐標就在短尺寸與大局部密度之間進行權衡，在節能的同時滿足網絡的二次抗毀性。如圖4所示，G2與G3之間最短的尺寸即M與N點，可是這兩種點的坐標并不是本文指定的區域，所以在這兩點里的隨機[12]一點的鄰居節點受到破壞時，那么該水下傳感器網絡的連通性就會出現二次毀壞的狀況。

圖4 精準連通恢復機制

2.4 相鄰兩種節點遭受二次損壞的狀況

2.4.1 選擇第二備用節點

針對兩種相鄰節點出現二次損毀的問題，選取備用節點的指標如下所示：

1)兩種關鍵節點不可以互相當做備用節點。

2)兩種相鄰的節點一種是非關鍵節點，一種是關鍵節點時：

假如非關鍵節點不是關鍵節點的備用節點，那么就不在需要第二備用節點。

假如非關鍵節點為關鍵節點的備用節點，那么從兩個節點的共同鄰居里挑選出一個第二備用節點；假如兩者沒有共通鄰居，那么就從關鍵節點里選擇一個節點作為第二備用節點。

3)兩種相鄰的節點都為關鍵節點時：

如果兩種節點都含有自己獨立的備用節點，那么不需要選取第二種備用節點。

如果兩種相鄰的掛件節點里一種即另一種的備用節點，那么需要選取第二種備用節點。

2.4.2 基于二次損壞的連通性恢復

針對水下傳感器網絡里兩種節點出現二次損壞的狀況，有一下幾種場景：

1)關鍵節點n1就是二次損毀的兩種相鄰節點，n2為非關鍵節點：

①假如n2不是n1的備用節點，那么n1的備用節點傳輸至n1的坐標就能夠對二次損壞的連通性進行恢復。如圖5里非關鍵節點N與關鍵節點M出現二次損壞，M的備用節點I轉移至M坐標即能夠恢復網絡連通性。

②如果n2代表n1的備用節點，那么就檢測第二備用節點的故障，并開始恢復連通性。如圖5里其備用節點R與關鍵節點L出現二次損壞，那么就通過第二備用節點X搜索非關鍵節點。進而獲得非關鍵節點C，如果得到非關鍵節點C，X，C就轉移至L級聯移動。

圖5 二次損壞連通性恢復

2)兩種節點n1，n2遭受二次損壞，并且節點都是關鍵節點：

①如果n1，n2都存在自己單獨的備用節點，同時都含有非關鍵節點，那么平行移動自身至相應的損壞節點就能夠恢復連通性。

②如果n1，n2都存在自己單獨的備用節點，同時兩個節點分別為關鍵節點與非關鍵節點，那么將非關鍵節點傳輸至關鍵節點的位置。之后運行非關鍵節點的搜索算法，從而獲得非關鍵節點，最后運行級聯移動，進而恢復網絡連通性。

③假如n1，n2都含有單獨的備用節點，同時都是關鍵的節點，那么兩種備用節點就同時使用非關鍵節點的搜索流程。經過防止沖突方式，搜索路徑里的每一個節點，如此反復知道完成搜索。

④如果n2是n1的備用節點，那么第二備用節點與n2的備用節點檢測到二次損壞出現，激活非關鍵節點的搜索流程。如圖5備用節點R與其關鍵節點L出現二次損壞，R的備用節點S找出R損壞，因為S即非關鍵節點，那么直接轉移至R坐標即可，節點R，X被第二備用節點B檢測到L損壞，并且找到非關鍵節點Q，然后Q，C，X往L級聯轉移。

3 仿真證明

仿真環境為Intel Celeron Tulatin1GHz CPU和384MB SD內存的硬件環境和MATLAB6.1的軟件環境。

為了證明本文方法的實用性，在水下環境1m*1m的范圍里隨機安放100種節點，并將其劃分為

1)移動尺寸，因為移動會耗費大量的水下傳感器資源，因此將水下傳感器的移動路徑最小化也是本文方法的設計目標之一。

2)最大移動尺寸，水下傳感器完成一種最短循環T所移動的最大尺寸L，假如L尺寸過大，就會導致自組織連通恢復出現延遲，因此需要最小化L。

在已經擬定完聚類數量的前提下，把本文方法與文獻[1]、文獻[2]方法進行對比，文獻方法的大體思想即在節點組成指定的數目集群后，每一種集群里選取一種收集點，通過最小生成樹對移動路徑進行估算，達到水下傳感器網絡節點移動最小化，進而節省節點的消耗。

表1 不同方法的移動總尺寸對比

通過表1能夠看出，本文方法要優于文獻方法，就是在水下傳感器網絡速度確定的狀態下，可以更好的恢復網絡的自組織連通性，同時節點組成六個集群時，本文方法明顯好過文獻方法。圖6為實驗圖像。

圖6 不同方法的移動總尺寸

表2是兩種方法的最大移動尺寸的對比。

表2 不同方法最大移動尺寸對比

通過表2能夠看出，本文方法在連通恢復效率上高過文獻方法，水下傳感器網絡運行的速度更快，其實驗圖像如圖7所示。

圖7 不同方法最大移動尺寸對比

通過表1、2的實驗結果能夠得知，在已組成指定聚類數量的前提下，本文方法能夠更快的對水下傳感器網絡自組織連通進行恢復，并且消耗的資源較少，更適合處理在水下環境內無人值守的傳感器網絡節點大規模損壞的恢復情況。

4 結論

針對水下傳感器連通受損恢復的問題，本文提出了一種水下傳感器網絡自組織連通恢復方法，通過分析水下傳感器網絡，確定傳感器網絡節點的中繼節點，然后使用MACRA算法對水下傳感器網絡分塊，以及節點密度計算進而恢復傳感器網絡的連通，并且為了防止二次破壞，還利用擬定閾值來選擇傳感器網絡的備用節點，使傳感器網絡即使遭受二次損壞也能夠及時的對其進行恢復。