圖論在計算機和無線傳感器網絡中的運用分析

孫帥

摘 要：21世紀，計算機技術的出現，從根本上改變了人類社會生產和生活方式，計算機憑借著強大、高速的計算能力，深入到現代科研、生產等多個領域，在其中占據著至關重要的位置。從某種意義上來說，計算機發展正推動者整個社會進步。圖論作為一種簡單、系統建模方式，能夠將問題轉換為圖論問題，然后運用圖論基本算法解決問題，以此來提高問題解決有效性。文章將從圖論相關內容入手，分析無線傳感器網絡中的聚類問題，并探討圖論在計算機與無線傳感器網絡中運用，最后基于上述研究內容對算法性能進行梳理。

關鍵詞：圖論；計算機；無線傳感器網絡；運用

近年來，人類社會正式進入到信息時代，移動傳感器網絡憑借自身在數據采集、魯棒性等方面具有的強大優勢，在軍用、民用等方面得到了廣泛應用，并能夠實現對環境高效監督和控制，且能夠提高防御效果。相比較具有固定設施的通信網絡，無線傳感器自身具有的組織機制，能夠賦予系統抗毀性、靈活性，但其自身實施對象能力存在一定局限性。故我們將圖論引入到計算機與無線傳感器網絡當中，能夠實現對通信效率、時機等要素進一步協調，以此來實現快速高效的網絡自組織，提高網絡運行有效性。

1 圖論概述

圖論是數學一部分，以圖為研究對象的理論。圖論當中的圖是由多個既定的點構成的圖形，這種圖形能夠描述某些事物之間特定關系，用點代表事物，運用連接點與點之間的線，能夠體現出事物之間的關系。圖論最早起源于非常經典的問題，即柯尼斯堡問題，歐拉是圖論創始人[1]。19世紀英國數學家漢密爾頓發明了一個游戲：運用規則實心十二面體，各個頂點標記為城市，游戲者要沿著各邊通過每個頂點形成閉回路。運用圖論語言來解釋，游戲的最終目的在于在十二面體圖中形成生成圈，正因為運籌學、計算機科學及編碼理論中的多數問題都可以運用漢密爾頓問題來解決，故引起了廣泛關注。

隨著無線通信技術快速發展，傳感器技術也隨之發展，傳感器具有的低成本、低能耗等優勢，在實踐應用中能夠有效感知周圍環境、簡單處理數據。通常來說，傳感器由感知、處理、收發及功能單元構成。在不同領域中的應用，還會增加定位器、能量產生單元等附加組件[2]。感知單元是整個傳感器的核心，由感知組件與模數轉換器構成，前者能夠感知地震波、聲波等參數。而后者能夠對不同格式的數據信息進行轉換。

2 無線傳感器網絡中的聚類問題

無線傳感器網絡存在能量限制，減少需要傳輸數據量，能夠有效節省節點能量。故在從不同節點收集數據過程中，可以在現有節點基礎上，實現對數據予以融合處理，消除冗余信息，以此來實現降低能量消耗的目標。但值得注意的是，節點易失效，影響數據融合效果，因此無線傳感器網絡，同樣要采用數據融合技術綜合數據，以此來提高信息準確度[3]。一般來說，當傳感器分布在范圍較大的區域、數量較多時，傳感器數據如何朝著融合中心傳輸成為亟待解決的關鍵問題。當前，現有技術發展水平下，可以構建三層分級網絡結構，并借助聚類算法。

聚類是一項數據分析技術，是將物理、抽象對象的集合，分組成由類似對象構成多個類的過程。但當前多數算法都集中在單一環境，很多應用中的數據源存在于網絡環境中，且聚類前，會數據采集到中心位置無法實現對數據信息的高效處理[4]。主要原因是，無線傳感器網絡中的有限通信寬帶，建立在感知節點之上，電池能源有限，無法確保網絡持續運行，但現有的聚類算法尚無法做到上述目標。圖2是圖論聚類算法框圖。

聚類算法按照既定的流程進行計算，能夠尋找到信息傳輸最佳路徑。

3 圖論在計算機與無線傳感器網絡中的運用

針對上文來看，將圖論應用到計算機、無線傳感器網絡當中，能夠盡最大限度收集覆蓋范圍所有點，且能夠有效彌補失效點，實現覆蓋范圍內數據傳輸有效性。為了進一步了解圖論對于無線傳感器網絡的積極作用，文章將進行詳細分析，具體如下：

3.1 圖廣度優先搜索算法

在實踐中，根據節點數量與需要分成的簇數需求，能夠獲得每個簇節點數，對整個圖廣度優先所搜記錄下節點數量，達到N/M后記所有節點，重新清零處理，直至整個圖完全遍歷完成后，將相鄰的節點劃分為M個子圖，子圖對應獨立簇。圖的廣度有限搜索算法具體流程如下：從圖中某一頂點出發，將其設置為VI，從該點出發，依次訪問所有沒有被訪問的鄰接點，如果圖中沒有被訪問的點，要從中選擇某一個作為起點，重復上述過程，完成對所有點的訪問。

3.2 簇內節點信息傳遞最優路徑實現

針對簇內信息傳遞來看，其目標是運用最小的能量代價，將信息傳給簇頭。本文選擇普里姆算法，實現對簇子圖優化構造和設計。普里姆算法是圖最小生成樹一種構造算法。假如WN=（V，{E}）中含有多個頂點連通網，TV是其中最小生成樹頂點集合。可見，完成算法執行時，開始時TE為空集，僅有一個頂點。故基于普里姆算法構造最小生成樹，即將所有點都集中在生成樹上，而另一頂點尚未落在生成樹上，取一條權值最小的邊，逐條加在生成樹上，完成所有點的結合。找出子圖最小生成樹后，可以選擇直接連接節點最多的節點作為簇頭，其他節點信息能夠通過不同渠道實現，最后由簇頭傳輸到數據融合中心，對數據信息進行分析和研究。

3.3 覆蓋與Voronoi圖

所謂覆蓋率，是指網絡能夠探測到目標范圍內，在目標區域總面積的占比，是評價自組織覆蓋算法好壞的具體標準。好的自組織算法，能夠使網絡盡可能最大限度上覆蓋目標區域，且能夠在部分傳感器節點失效情況下，進行網絡調整和優化，以此來實現對失效節點的有效彌補。Voronoi圖（如圖3）是提高某些算法運算速度的主要方式和方法。通常而言，二維圖形能夠在特定時間范圍內獲取，而三維圖獲得信息時間較長，Voronoi圖性質決定了其與很多幾何結構存在密切聯系，通過該圖，很多集合算法能夠快速實現，提高運算效率。值得我們注意的是，如果某個二維、三維點集中在四點共圓當中，此時，這些點對應的多邊形中會有一個頂點。這些點相互連接，最終形成了不同的形狀。綜上來看，在二維、三維傳感器節點自組織中，只要節點探測半徑范圍內形成的圓，能夠包圍住多邊形，實現全面覆蓋。

3.4 連接與三角剖分

連接目的是將網絡構成一個整體，如果網絡分化為多個不相連的子網絡，其中部分子網絡感知到的信息，將會成為無效信息。故我們希望網絡中彼此都能夠相互連接，確保整個網絡協調、有序運轉。實踐中，在圖論理論基礎之上，三角形網格圖中，稱一條內邊e是局部優化，指共享e的兩個三角形對應形成的四邊形能夠形成較好的部分。簡而言之，如果e具有局部優化，那么形成的四邊形不存在凹多邊形。稱三角形網格是全局優化的，如果它所在內邊具有局部優化，可以證明在特定節點集合所有網格當中，全局優化三角形網絡具有最優性。通過上述分析，運用這種方式，在三角形網格中，各個節點之間的信息能夠相互傳遞。

無線傳感器網絡自組織度衡量所有節點，自組織貢獻率存在差異性。一般情況下，自組織越大，節點自身自組織貢獻率差異性，網絡自組織演化，對少數節點、節點集依賴性相對較小，因而網絡更具魯棒性。正因如此，圖論對于無線傳感器具有的促進作用使得二者能夠深入整合。

4 算法性能分析

文章在PC機上運用VC++6.0編程環境，實現上述算法，通過多線工作方式模擬無線傳感器網絡工作環境。在仿真中，將無線傳感器網絡在圖論上的分布式聚類算法與所有數據傳回，并進行統一計算和處理，通過對二者性能進行比對，最后確定出隨著網絡節點數量增加，算法執行時間變化情況。根據上述內容形成比較曲線，如圖4，其中橫坐標與縱坐標分別代表的是節點數目、時間，從仿真實驗結果中發現，圖論分布式聚類算法較傳統集中算法性能更好。

為了驗證網絡魯棒性，我們在節點自組織穩定后，從中隨機拿掉兩個節點，觀察網絡再組織能力獲得仿真效果。根據仿真結果來看，隨機減少的兩個節點，傳感器網絡依舊能夠良好地進行再組織，不僅能夠有效彌補失去節點的空白，且能夠使得網絡對劃定區域保持較高的覆蓋率，使得網絡更具整體性。另外，通過觀察自組織曲線來看，當網絡處于穩定狀態后，虛擬里自組織辦法能夠使傳感器網絡在自組織過程中，保持較高的自組織度，且能夠實現進一步優化。雖然網絡節點有所減少，自組織度會下降。但在虛擬里的作用下，網絡能夠在短時間恢復到最佳狀態，不斷對其進行優化，可見網絡魯棒性、靈活性較好。隨著科學技術不斷發展，計算機與無線傳感器網絡在未來社會發展中的應用范圍將會越來越廣，對此我們還要增加資金、人力等方面投入，加大研究力度，進一步深化無線傳感器結構與性能，使其能夠在應用中充分發揮積極作用。

5 結論

根據上文所述，無線傳感器網絡在實踐應用中，強調的是無線傳感器網絡由無到有、從小至大的過程。該網絡憑借自身較好的魯棒性、高效性及靈活性等優勢，在實踐中得到了廣泛應用。而圖論理論的提出和應用，為進一步優化網絡性能提供了極大的支持。文章從覆蓋、連接等多個方面對圖論在計算機與無線傳感器網絡中運用進行分析和研究，并對算法在實踐應用中產生的性能進行驗證發現，圖論對于無線傳感器網絡良好運行具有積極作用，能夠及時發現其中的問題，并采取相應的措施加以規范和優化，不斷提高網絡運行有效性，從而為相關領域持續發展奠定堅實的基礎。

參考文獻

[1]李琳.無線傳感器網絡路由算法仿真模型的研究[J].電腦開發與應用，2014，（4）：27-29，32.

[2]師超，仇洪冰，陳東華，等.一種簡單的分布式無線傳感器網絡時間同步方案[J].西安電子科技大學學報，2013，（1）：93-99，147.

[3]何劍海.無線傳感器網絡定位技術在農田復雜環境中的應用[J].無線互聯科技，2013，（2）：187-188.

[4]肖大威.無線傳感器網絡中數據存儲與訪問進展分析[J].電子制作，2013，（9）：149.

（作者單位：北京郵電大學）