無線傳感器網絡自愈修複方法及系統與流程
2023-06-09 07:40:31 4
本發明涉及無線傳感
技術領域：
，尤其是涉及一種無線傳感器網絡自愈修複方法及系統。
背景技術：
：無線傳感器網絡常被部署在條件惡劣的環境中，因此網絡容易發生各種故障。當部署之後的網絡發生局部故障，如關鍵節點故障等，將可能影響網絡的正常工作，此時需要有效的機制對故障的網絡進行修復。在單個節點故障的情況下，當網絡中的其他節點可移動時，可採用移動節點的方式來修復網絡連接。採用移動節點的修複方法，一方面無需部署新的節點，節省了購買設備的開銷；另一方面，這種方法可以由預先制定的修復算法自動完成，無需人工幹預，節省了人工修復成本。但採用這種方法進行修復也面臨著兩方面的挑戰。第一，這種修複方法的一般步驟是將故障節點的鄰居節點往故障節點的位置移動，目的是讓鄰居節點完全替代故障節點，從而修復網絡連接。但鄰居節點的移動可能會導致其他連接斷開，帶來新的網絡故障問題。因此，如何適當地移動鄰居節點而不引起新的網絡故障是本發明需要解決的一個問題。第二，與節點處於靜止狀態相比，節點的移動需要耗費額外的能量。若原本能量剩餘不多的節點耗費過多的能量進行移動，則該節點可能在到達指定位置之前便失效，或者在移動到指定位置之後不久便失效。節點失效也可能帶來新的網絡故障問題。因此，如果適當地移動各個節點，使得移動之後的節點還能較長久地在網絡中提供服務是本發明需要考慮的另一個問題。現有方法主要注重於修復網絡的連接，並未同時考慮上述兩方面問題。Younis等人提出的RIM算法的修復步驟為：當網絡中某個關鍵節點故障時，其所有鄰居節點同時向故障節點方向移動，直到鄰居節點之間可以相互通信為止。鄰居節點的移動若導致其他連接的斷開，則這些斷開的連接也通過節點同時移動的方法進行修復。也就是說，當網絡中某個關鍵節點故障時，通過所有節點一起向故障節點位置移動的方式來達到修復網絡連接的目標。這種方法雖然修復了網絡連接，但導致了網絡中大部分節點都需要移動。Abbasi等人在RIM算法的基礎上進行改進，提出了DARA算法。當網絡中某個關鍵節點故障時，DARA算法將節點度最小的鄰居節點移動到故障節點位置。若鄰居節點的移動帶來了新的網絡連接的斷開，則其他節點通過級聯移動的方式來修復網絡連接。儘管該算法修復了網絡連接，但當移動的節點也處於網絡中的關鍵位置時，這種移動方法同樣導致了較多節點的移動。此外，Abbasi等人還提出了LeDiR算法，該算法假設當網絡中某個關鍵節點故障時，網絡至少被分為兩個子塊。該算法首先找到所有分塊中的最小子塊，並在最小子塊中找到故障節點的鄰居節點。其次，將鄰居節點移動到故障節點位置，代替故障節點執行指定功能。若鄰居節點的移動帶來了新的網絡連接的斷開，則其鄰居節點向故障節點方向移動，直到修復網絡連接為止。與RIM和DARA算法相比，LeDiR算法相對地減少了移動節點的數目。Tamboli等人提出的ECR算法通過輪流將故障節點的鄰居移動到故障節點的位置來達到修復網絡連接和維持原有覆蓋的目的，但從該算法開始執行之後，節點一直處於輪流移動狀態，整個網絡十分不穩定。上述算法均是在單個節點故障的情況下對網絡連接進行修復，並要求網絡中的其他節點可移動。通過行動網路中的其他節點，可在無需人工幹預的情況下，網絡自行修復連接，不僅節約人工修復的成本，也節約了購買設備的成本。但是上述算法均未考慮節點的能量問題。若節點本身剩餘能量較少，卻仍要按照算法的要求進行移動，則很可能導致節點在沒有移動到指定位置之前，就因能量耗盡而死亡，進而導致更嚴重的網絡故障。因此，對於單個節點故障的情況，在制定修復策略時，需要同時考慮節點的能量問題。技術實現要素：本發明所要解決的技術問題是：提供一種無線傳感器網絡有效的自愈修複方法，以平衡節點能耗，延長網絡生存周期。為了解決上述技術問題，本發明採用的技術方案為：提供一種無線傳感器網絡自愈修複方法，包括：獲取無線傳感器節點的位置坐標以及關鍵節點；在檢測關鍵節點發生故障後，根據節點能量，朝故障關鍵節點方向移動其對應的鄰居節點；在移動鄰居節點後，檢測是否修復網絡連接；若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。為解決上述問題，本發明還提供一種無線傳感器網絡自愈修復系統，包括：目標獲取單元，用於獲取無線傳感器節點的位置坐標以及關鍵節點；節點移動單元，用於在檢測關鍵節點發生故障後，根據節點能量，朝故障關鍵節點方向移動其對應的鄰居節點；連接檢測單元，用於檢測在移動鄰居節點後，檢測是否修復網絡連接；子塊移動單元，用於若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。本發明的有益效果在於：區別於現有技術，本發明確定故障關鍵節點後，根據其鄰居節點能量，朝故障關鍵節點方向進行移動，並初次檢測是否修復網絡連接；若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。通過上述方式，本發明不僅最大程度地保持了節點原有的連接，還有效地平衡了節點的能耗，延長了網絡的生存周期。附圖說明圖1為本發明具體實施例的操作流程示意圖；圖2為本發明具體實施例中無線傳感器網絡示意圖；圖3為本發明具體實施例中ni+1節點故障後進行相切移動示意圖；圖4為本發明具體實施例中的SER算法與現有的LeDiR算法的總移動距離對比曲線圖；圖5為本發明具體實施例中的SER算法與現有的LeDiR算法的總能耗對比曲線圖；圖6為本發明具體實施例中的SER算法與現有的LeDiR算法的總移動節點數目對比曲線圖；圖7為本發明具體實施例中的SER算法與現有的LeDiR算法的能量方差對比曲線圖。具體實施方式為詳細說明本發明的技術內容、所實現目的及效果，以下結合實施方式並配合附圖予以說明。本發明最關鍵的構思在於：確定關鍵節點發生故障後，根據鄰居節點能量，向關鍵節點方向移動，以檢測是否修復網絡連接。本發明實施例一提供一種無線傳感器網絡自愈修複方法，包括：獲取無線傳感器節點的位置坐標以及關鍵節點；在檢測關鍵節點發生故障後，根據節點能量，朝故障關鍵節點方向移動其對應的鄰居節點；在移動鄰居節點後，檢測是否修復網絡連接；若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。區別於現有技術，本發明確定故障關鍵節點後，根據其鄰居節點能量，朝故障關鍵節點方向進行移動，並初次檢測是否修復網絡連接；若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。通過上述方式，本發明不僅最大程度地保持了節點原有的連接，還有效地平衡了節點的能耗，延長了網絡的生存周期。其中，每個節點定期向其鄰居節點發送心跳消息；鄰居節點判斷在特定時間段內是否接收到心跳消息，若是，則表示該節點正常；反之，則表示該節點發送故障，並判斷該節點是否為關鍵節點，若是，則朝故障關鍵節點方向移動其對應的鄰居節點；反之，則忽略該節點。在移動時，需要預先獲取發生故障的關鍵節點的鄰居節點的初始能量，並按照能量高低進行排序；按照初始能量高低，依序為每個鄰居節點計算相切距離及允許移動距離；取相切距離及允許移動距離中的較小值，作為該鄰居節點的移動距離；朝故障關鍵節點方向移動該鄰居節點的所述移動距離後，判斷是否修復網絡連接；若是，則表示修復成功，並結束流程；反之，則為初始能量第二大的鄰居節點計算相切距離及允許移動距離，並進行移動；直至關鍵節點的所有鄰居節點都進行移動為止。若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信，具體為：通過關鍵節點，對無線傳感器節點劃分若干個子塊；比較各個子塊包含的節點數目，獲取無線傳感器節點的最小塊；向故障關鍵節點方向移動最小塊的鄰居節點，直到鄰居節點可以與故障節點的其他鄰居節點進行通信。若最小快鄰居節點的移動造成新的連接斷開，則將其他節點朝故障關鍵節點方向移動，直至完成網絡連接的修復。對應地，本發明實施例二提供一種無線傳感器網絡自愈修復系統，包括：目標獲取單元，用於獲取無線傳感器節點的位置坐標以及關鍵節點；節點移動單元，用於在檢測關鍵節點發生故障後，根據節點能量，朝故障關鍵節點方向移動其對應的鄰居節點；連接檢測單元，用於檢測在移動鄰居節點後，檢測是否修復網絡連接；子塊移動單元，用於若未修復，則朝故障關鍵節點方向移動節點最小塊，直至所有子塊可相互通信。其中，每個節點定期向其鄰居節點發送心跳消息；鄰居節點判斷在特定時間段內是否接收到心跳消息，若是，則表示該節點正常；反之，則表示該節點發送故障，並判斷該節點是否為關鍵節點，若是，則朝故障關鍵節點方向移動其對應的鄰居節點；反之，則忽略該節點。所述節點移動單元還用於：獲取發生故障的關鍵節點的鄰居節點的初始能量，並按照能量高低進行排序；按照初始能量高低，依序為每個鄰居節點計算相切距離及允許移動距離；取相切距離及允許移動距離中的較小值，作為該鄰居節點的移動距離；朝故障關鍵節點方向移動該鄰居節點的所述移動距離後，判斷是否修復網絡連接；若是，則表示修復成功，並結束流程；反之，則為初始能量第二大的鄰居節點計算相切距離及允許移動距離，並進行移動；直至關鍵節點的所有鄰居節點都進行移動為止。所述子塊移動單元具體用於：通過關鍵節點，對無線傳感器節點劃分若干個子塊；比較各個子塊包含的節點數目，獲取無線傳感器節點的最小塊；向故障關鍵節點方向移動最小塊的鄰居節點，直到鄰居節點可以與故障節點的其他鄰居節點進行通信。若最小快鄰居節點的移動造成新的連接斷開，則將其他節點朝故障關鍵節點方向移動，直至完成網絡連接的修復。為方便理解，以下結合附圖1～7，通過一個具體實施例進行說明。本發明的無線傳感器網絡能量有效的自愈修複方法。該方法大體上可分成移動鄰居節點以及移動最小塊兩個步驟。在移動鄰居節點步驟中，節點最終移動的距離取決於節點與其鄰居之間的覆蓋重疊情況以及節點本身的能量情況。若所有鄰居節點移動後均未能修復網絡連接，則移動最小塊。在移動最小塊步驟中，節點移動的首要目標是修復網絡連接，因此這個步驟並未考慮節點的能量問題，而是將處於最小塊的節點進行移動以修復網絡連接。該方法不僅最大程度地保持了節點原有的連接，還有效地平衡了節點的能耗，延長了網絡的生存周期。首先假設無線傳感器網絡中的節點均可移動，並且發生故障的節點為關鍵節點。當把一個節點及其相關的邊都移除，若整個網絡被分割成2個或2個以上的子塊，則稱該節點為關鍵節點，因此關鍵節點包括至少2邊。圖2中，當節點n5及其相應的邊被移除時，整個網絡被分割成三個子塊，因此，節點n5稱為關鍵節點。類似的，n2、n3和n7也均為關鍵節點。相反地，節點n1、n4、n6和n8稱為葉子節點。相比於關鍵節點，葉子節點發生故障時，對整個網絡的影響相對較小。因此在單節點故障的問題中，本發明主要關注的是某個關鍵節點故障時，如何適當地行動網路中其他節點來修復網絡連接，使得修復之後的網絡可以正常通信。無線傳感器網絡中的節點通常隨機部署，導致部署之後節點與節點之間存在較大的覆蓋重疊區域。因此，當網絡中某個節點需要移動時，本發明採用的方法之一是將該節點移動到與其鄰居節點相切的位置，這樣既維持了節點的原有連接，也擴大了覆蓋面積。但是，若節點與其鄰居節點的覆蓋重疊區域較大，則節點需要移動較長的距離才能到達與鄰居節點相切的位置，這將導致節點需要耗費較多的能量。但節點所擁有的能量並不一定能提供節點的較長移動。因此，為了維持節點原有連接，同時使得節點在移動之後可以繼續提供服務，本發明為節點設置了一個能量閾值，只有節點的能量大於閾值才進行移動。所以，在本發明中需要為每個即將移動的節點計算兩個值：節點從初始位置移動到與鄰居節點相切的位置的移動距離(相切距離)，以及節點擁有的能量所能提供節點移動的距離(最大距離)，並取其中較小的一個值為節點的最終移動距離。以圖3為例，當節點ni+1故障時，需要移動ni+1的鄰居節點ni或ni+2去修復網絡連接。假設ni和ni+2現有的能量均大於閾值，並且ni的能量大於ni+2的能量。首先將ni朝ni+1方向移動。ni可移動的距離取決於ni與其鄰居節點ni-1之間的覆蓋重疊情況以及ni自身的能量值。下面分別計算ni的相切距離和最大移動距離。在圖3中，假設節點ni、ni-1和ni+1的初始坐標分別為(xi,yi)、(xi-1,yi-1)和(xi+1,yi+1)，ni移動到與節點ni-1相切的位置之後的坐標為(x,y)。各個節點的初始坐標已知，(x,y)未知。因為ni往ni+1方向移動，所以有yi+1-yixi+1-xi=y-yix-xi---(1-1)]]>ni與ni-1相切，有(x-xi-1)2+(y-yi-1)2＝(2×R)2(1-2)聯立(2-1)和(2-2)兩個等式即可求解(x,y)。通過(x,y)可求得節點ni的移動距離，即相切距離，為dtani=(x-xi)2+(y-yi)2---(1-3)]]>此外，還需計算ni的最大移動距離。假設節點ni所具有的能量為ei，可用於移動的能量(稱為額外能量)為ei-et(ei>et)。並假設節點每移動單位距離需要耗費的能量為ed，則ni可以移動的最大距離為dmaxi=ei-eted---(1-4)]]>最後取dtani和dmaxi二者之中的較小值為節點的最終移動距離。這樣既保證了節點之間的原有連接不被破壞，也保證了節點在移動之後還能有足夠的能量繼續為網絡提供服務。如圖1所示，本發明所述的無線傳感器網絡能量有效的自愈修復算法(SER)步驟如下：步驟1.初始化。在節點部署之後，假設節點可以通過GPS等技術獲取自己所在的位置坐標。通過解析路由表，每個節點都知道網絡中哪些節點為關鍵節點。步驟2.故障檢測。每個節點定期地向其鄰居節點發送心跳消息。一旦某個節點的鄰居節點在一段時間內沒有收到該節點發送的心跳消息，則認為該節點發生故障。故障節點的鄰居節點判斷故障節點是否為關鍵節點，若為關鍵節點，則執行以下步驟。步驟3.移動鄰居節點。假設故障節點為nF，該節點有m個鄰居節點，每個鄰居節點具有不同的初始能量ei。設nF的鄰居節點集合為Snb＝{n1,n2,…,nm}。當鄰居節點檢測到nF發生故障時，鄰居節點中具有最大能量值的節點ni計算自己的dtani和dmaxi的值(ei>et)，並選擇其中較小的一個值為其移動距離。若dtani值較小，則說明ni需要朝故障節點方向移動到與其鄰居節點相切的位置；反之，若dmaxi值較小，則說明ni朝故障節點方向移動dmaxi距離。無論節點移動dtani或dmaxi距離，都不會破壞節點與其鄰居節點之間的連接。移動結束之後，ni判斷自己是否修復了網絡連接。若已經修復完成，整個網絡可以正常通信，則終止修復算法；若ni移動之後網絡連接還未修復完成，則具有第二高能量值的節點nj計算自己的dtanj和dmaxj的值後，執行與ni相同的步驟。若nF所有的鄰居節點都移動之後，網絡連接仍未修復完成，即對應圖1中，按照能量大小，逐一移動故障關鍵節點的鄰居節點，並逐一從該Snb＝{n1,n2,…,nm}中刪除，直到鄰居節點均移動(即集合Snb＝{n1,n2,…,nm}為空時)，若網絡連接仍未修復，則執行步驟4。步驟4.移動最小塊。最小塊指的是在由故障節點斷開而導致的所有分塊當中具有節點數目最少的子塊。當故障節點的鄰居節點都移動完畢之後網絡連接還未被修復，此時需要找到所有分塊中的最小塊，將處於最小塊的節點向故障節點方向移動，直至所有子塊能夠相互通信。具體做法為：處於最小塊中的故障節點對應的鄰居節點向故障節點移動，逐一移動整個最小塊的所有節點，直到鄰居節點可以與故障節點的其他鄰居節點進行通信。若鄰居節點的移動帶來了新的連接的斷開，則將其他節點朝故障節點方向移動，直至完成網絡連接的修復。在本發明的步驟3中，所有滿足能量閾值的節點在連接修復完成之前均需要向故障節點方向移動。算法通過設置閾值的方式，避免某個節點將能量提前耗盡，也通過這種方法使得參與修復的每個節點的能量達到相對的均衡。步驟4表明，一個節點的移動可能導致一批節點都需要移動，但因為這些節點均處於最小塊(節點數目最少的子塊)，所以總的移動的節點數目將不會太多。此外，從修復算法的各個步驟中可以看出，不管是移動鄰居節點或是移動最小塊，節點之間的最短路徑都沒有被延長。令為節點在修復過程中移動的總距離。假設修復算法執行完畢後共有個節點進行移動，則這些節點的總的移動距離為Dsum=Σi=1kdi---(3-1)]]>由於每個節點移動單位距離需要耗費的能量為，因此這些節點需耗費的總能量為Esum=ed×Dsum=ed×Σi=1kdi---(3-2)]]>每個節點初始的能量為，移動之後剩餘的能量為ei-ed×di(3-3)每個節點移動之後的平均剩餘能量為Ea=1kΣi=1k(ei-ed×di)---(3-4)]]>剩餘能量的方差為V=1kΣi=1k(ei-ed×di-Ea)2=1kΣi=1k(ei-ed×di-1kΣi=1k(ei-ed×di))2---(3-5)]]>修復之後，這些移動的節點所能存活的時間為T=min{ei-ed×di}es,1≤i≤k.---(3-6)]]>將本發明與LeDiR算法進行比較。在仿真實驗中，節點部署的區域為固定大小。圖4描述的是固定區域內節點的數目與節點總移動距離之間的關係。從圖4中可以看出，隨著節點數目的增大，兩種修復算法的總移動距離均隨之減小。這是因為當區域面積固定時，部署的節點數目越多，節點越密集，節點之間相隔的距離越小。當某個節點發生故障時，其鄰居節點所需移動的距離也將縮短。另一方面，從圖4也可以看出，本發明的SER算法總移動距離小於LeDiR算法。這是因為LeDiR直接移動整個最小塊，這種方法等同於讓單個鄰居節點移動較長的距離來修復網絡連接。單個節點移動較長距離很大程度上引起了新的連接的斷開，此時需要其他單個節點也移動較長的距離來修復。也就是說，LeDiR算法的修復過程像是單個節點的移動修復，而本發明的SER算法類似於各個鄰居節點之間協同工作來實現網絡連接修復，鄰居節點之間的協同工作能更好地縮短移動距離，因此本發明的SER算法比LeDiR算法的節點總移動距離更短。從公式可以看出，所有移動節點所消耗的能量與節點所移動的距離成正比，因此圖5的曲線類似於圖4的曲線。也就是說，當一個固定區域內部署的節點數目增加時，節點之間的距離變小，當某個節點發生故障後，參與修復的所有節點所移動的總距離變小，節點所消耗的總能量也變小。從圖5中可以看出，本發明的SER算法的節點所耗費的總能量小於LeDiR算法。這是因為，本發明的SER算法的節點所移動的總距離小於LeDiR算法節點移動的總距離。圖6描述的是固定區域內節點的數目與總移動節點數之間的關係。在實際應用中，固定區域中部署的節點數目越多，節點之間的距離便隨之減小。當某個節點發生故障時，修復過程中所需移動的節點數目便減少了。圖6的曲線趨勢符合實際應用情況。從圖6中也可以看出，本發明的SER算法移動的節點數目多於LeDiR算法。這是因為LeDiR算法在進行網絡連接修復時，直接移動處於最小子塊的鄰居節點。在最壞的情況下，LeDiR算法需要移動的節點數目為最小子塊中所有節點的個數，而本發明的SER算法在最壞的情況下需要移動的節點數目為最小子塊中所有節點的個數與故障節點的所有鄰居節點個數之和。因此從最壞的情況來看，本發明的SER算法所移動的節點數目將會大於LeDiR算法所移動的節點數目。而一般的情況下，本發明的SER算法因為需要幾乎所有鄰居的協同合作，而LeDiR算法只需移動最小塊的部分節點，所以從一般情況下來看，本發明的SER算法所需移動的節點數目也會大於LeDiR算法。節點的能量方差反映的是節點的能量均衡情況。當網絡中各個節點所擁有的能量越均衡時，網絡越不容易因為單個節點的能量耗盡而產生新的網絡故障問題，網絡的存活時間就越長。因此，節點的能量方差間接地反映了網絡的生存周期。由方差的定義可知，方差越小表示各個數值越均衡。所以，節點的能量方差越小，代表了節點的剩餘能量越均衡，網絡的生存周期便越長。從圖7中可以看出，與LeDiR算法相比，本發明的SER算法修復之後的網絡具有更小的方差值，說明在本發明的SER算法修復之後的網絡中，各個節點所具有的能量更均衡，網絡能夠有更長的生存周期。本發明提供的無線傳感器網絡能量有效的自愈修複方法，可以平衡節點能耗，延長網絡生存周期。以上所述僅為本發明的實施例，並非因此限制本發明的專利範圍，凡是利用本發明說明書及附圖內容所作的等同變換，或直接或間接運用在相關的
技術領域：
，均同理包括在本發明的專利保護範圍內。當前第1頁1 2 3