圖論在計(jì)算機(jī)和無線傳感器網(wǎng)絡(luò)中的運(yùn)用分析

孫帥

摘 要：21世紀(jì)，計(jì)算機(jī)技術(shù)的出現(xiàn)，從根本上改變了人類社會(huì)生產(chǎn)和生活方式，計(jì)算機(jī)憑借著強(qiáng)大、高速的計(jì)算能力，深入到現(xiàn)代科研、生產(chǎn)等多個(gè)領(lǐng)域，在其中占據(jù)著至關(guān)重要的位置。從某種意義上來說，計(jì)算機(jī)發(fā)展正推動(dòng)者整個(gè)社會(huì)進(jìn)步。圖論作為一種簡單、系統(tǒng)建模方式，能夠?qū)栴}轉(zhuǎn)換為圖論問題，然后運(yùn)用圖論基本算法解決問題，以此來提高問題解決有效性。文章將從圖論相關(guān)內(nèi)容入手，分析無線傳感器網(wǎng)絡(luò)中的聚類問題，并探討圖論在計(jì)算機(jī)與無線傳感器網(wǎng)絡(luò)中運(yùn)用，最后基于上述研究內(nèi)容對(duì)算法性能進(jìn)行梳理。

關(guān)鍵詞：圖論；計(jì)算機(jī)；無線傳感器網(wǎng)絡(luò)；運(yùn)用

近年來，人類社會(huì)正式進(jìn)入到信息時(shí)代，移動(dòng)傳感器網(wǎng)絡(luò)憑借自身在數(shù)據(jù)采集、魯棒性等方面具有的強(qiáng)大優(yōu)勢，在軍用、民用等方面得到了廣泛應(yīng)用，并能夠?qū)崿F(xiàn)對(duì)環(huán)境高效監(jiān)督和控制，且能夠提高防御效果。相比較具有固定設(shè)施的通信網(wǎng)絡(luò)，無線傳感器自身具有的組織機(jī)制，能夠賦予系統(tǒng)抗毀性、靈活性，但其自身實(shí)施對(duì)象能力存在一定局限性。故我們將圖論引入到計(jì)算機(jī)與無線傳感器網(wǎng)絡(luò)當(dāng)中，能夠?qū)崿F(xiàn)對(duì)通信效率、時(shí)機(jī)等要素進(jìn)一步協(xié)調(diào)，以此來實(shí)現(xiàn)快速高效的網(wǎng)絡(luò)自組織，提高網(wǎng)絡(luò)運(yùn)行有效性。

1 圖論概述

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

隨著無線通信技術(shù)快速發(fā)展，傳感器技術(shù)也隨之發(fā)展，傳感器具有的低成本、低能耗等優(yōu)勢，在實(shí)踐應(yīng)用中能夠有效感知周圍環(huán)境、簡單處理數(shù)據(jù)。通常來說，傳感器由感知、處理、收發(fā)及功能單元構(gòu)成。在不同領(lǐng)域中的應(yīng)用，還會(huì)增加定位器、能量產(chǎn)生單元等附加組件[2]。感知單元是整個(gè)傳感器的核心，由感知組件與模數(shù)轉(zhuǎn)換器構(gòu)成，前者能夠感知地震波、聲波等參數(shù)。而后者能夠?qū)Σ煌袷降臄?shù)據(jù)信息進(jìn)行轉(zhuǎn)換。

2 無線傳感器網(wǎng)絡(luò)中的聚類問題

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

聚類是一項(xiàng)數(shù)據(jù)分析技術(shù)，是將物理、抽象對(duì)象的集合，分組成由類似對(duì)象構(gòu)成多個(gè)類的過程。但當(dāng)前多數(shù)算法都集中在單一環(huán)境，很多應(yīng)用中的數(shù)據(jù)源存在于網(wǎng)絡(luò)環(huán)境中，且聚類前，會(huì)數(shù)據(jù)采集到中心位置無法實(shí)現(xiàn)對(duì)數(shù)據(jù)信息的高效處理[4]。主要原因是，無線傳感器網(wǎng)絡(luò)中的有限通信寬帶，建立在感知節(jié)點(diǎn)之上，電池能源有限，無法確保網(wǎng)絡(luò)持續(xù)運(yùn)行，但現(xiàn)有的聚類算法尚無法做到上述目標(biāo)。圖2是圖論聚類算法框圖。

聚類算法按照既定的流程進(jìn)行計(jì)算，能夠?qū)ふ业叫畔鬏斪罴崖窂健?/p>

3 圖論在計(jì)算機(jī)與無線傳感器網(wǎng)絡(luò)中的運(yùn)用

針對(duì)上文來看，將圖論應(yīng)用到計(jì)算機(jī)、無線傳感器網(wǎng)絡(luò)當(dāng)中，能夠盡最大限度收集覆蓋范圍所有點(diǎn)，且能夠有效彌補(bǔ)失效點(diǎn)，實(shí)現(xiàn)覆蓋范圍內(nèi)數(shù)據(jù)傳輸有效性。為了進(jìn)一步了解圖論對(duì)于無線傳感器網(wǎng)絡(luò)的積極作用，文章將進(jìn)行詳細(xì)分析，具體如下：

3.1 圖廣度優(yōu)先搜索算法

在實(shí)踐中，根據(jù)節(jié)點(diǎn)數(shù)量與需要分成的簇?cái)?shù)需求，能夠獲得每個(gè)簇節(jié)點(diǎn)數(shù)，對(duì)整個(gè)圖廣度優(yōu)先所搜記錄下節(jié)點(diǎn)數(shù)量，達(dá)到N/M后記所有節(jié)點(diǎn)，重新清零處理，直至整個(gè)圖完全遍歷完成后，將相鄰的節(jié)點(diǎn)劃分為M個(gè)子圖，子圖對(duì)應(yīng)獨(dú)立簇。圖的廣度有限搜索算法具體流程如下：從圖中某一頂點(diǎn)出發(fā)，將其設(shè)置為VI，從該點(diǎn)出發(fā)，依次訪問所有沒有被訪問的鄰接點(diǎn)，如果圖中沒有被訪問的點(diǎn)，要從中選擇某一個(gè)作為起點(diǎn)，重復(fù)上述過程，完成對(duì)所有點(diǎn)的訪問。

3.2 簇內(nèi)節(jié)點(diǎn)信息傳遞最優(yōu)路徑實(shí)現(xiàn)

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

3.3 覆蓋與Voronoi圖

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

3.4 連接與三角剖分

連接目的是將網(wǎng)絡(luò)構(gòu)成一個(gè)整體，如果網(wǎng)絡(luò)分化為多個(gè)不相連的子網(wǎng)絡(luò)，其中部分子網(wǎng)絡(luò)感知到的信息，將會(huì)成為無效信息。故我們希望網(wǎng)絡(luò)中彼此都能夠相互連接，確保整個(gè)網(wǎng)絡(luò)協(xié)調(diào)、有序運(yùn)轉(zhuǎn)。實(shí)踐中，在圖論理論基礎(chǔ)之上，三角形網(wǎng)格圖中，稱一條內(nèi)邊e是局部優(yōu)化，指共享e的兩個(gè)三角形對(duì)應(yīng)形成的四邊形能夠形成較好的部分。簡而言之，如果e具有局部優(yōu)化，那么形成的四邊形不存在凹多邊形。稱三角形網(wǎng)格是全局優(yōu)化的，如果它所在內(nèi)邊具有局部優(yōu)化，可以證明在特定節(jié)點(diǎn)集合所有網(wǎng)格當(dāng)中，全局優(yōu)化三角形網(wǎng)絡(luò)具有最優(yōu)性。通過上述分析，運(yùn)用這種方式，在三角形網(wǎng)格中，各個(gè)節(jié)點(diǎn)之間的信息能夠相互傳遞。

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

4 算法性能分析

文章在PC機(jī)上運(yùn)用VC++6.0編程環(huán)境，實(shí)現(xiàn)上述算法，通過多線工作方式模擬無線傳感器網(wǎng)絡(luò)工作環(huán)境。在仿真中，將無線傳感器網(wǎng)絡(luò)在圖論上的分布式聚類算法與所有數(shù)據(jù)傳回，并進(jìn)行統(tǒng)一計(jì)算和處理，通過對(duì)二者性能進(jìn)行比對(duì)，最后確定出隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量增加，算法執(zhí)行時(shí)間變化情況。根據(jù)上述內(nèi)容形成比較曲線，如圖4，其中橫坐標(biāo)與縱坐標(biāo)分別代表的是節(jié)點(diǎn)數(shù)目、時(shí)間，從仿真實(shí)驗(yàn)結(jié)果中發(fā)現(xiàn)，圖論分布式聚類算法較傳統(tǒng)集中算法性能更好。

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

5 結(jié)論

根據(jù)上文所述，無線傳感器網(wǎng)絡(luò)在實(shí)踐應(yīng)用中，強(qiáng)調(diào)的是無線傳感器網(wǎng)絡(luò)由無到有、從小至大的過程。該網(wǎng)絡(luò)憑借自身較好的魯棒性、高效性及靈活性等優(yōu)勢，在實(shí)踐中得到了廣泛應(yīng)用。而圖論理論的提出和應(yīng)用，為進(jìn)一步優(yōu)化網(wǎng)絡(luò)性能提供了極大的支持。文章從覆蓋、連接等多個(gè)方面對(duì)圖論在計(jì)算機(jī)與無線傳感器網(wǎng)絡(luò)中運(yùn)用進(jìn)行分析和研究，并對(duì)算法在實(shí)踐應(yīng)用中產(chǎn)生的性能進(jìn)行驗(yàn)證發(fā)現(xiàn)，圖論對(duì)于無線傳感器網(wǎng)絡(luò)良好運(yùn)行具有積極作用，能夠及時(shí)發(fā)現(xiàn)其中的問題，并采取相應(yīng)的措施加以規(guī)范和優(yōu)化，不斷提高網(wǎng)絡(luò)運(yùn)行有效性，從而為相關(guān)領(lǐng)域持續(xù)發(fā)展奠定堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)

[1]李琳.無線傳感器網(wǎng)絡(luò)路由算法仿真模型的研究[J].電腦開發(fā)與應(yīng)用，2014，（4）：27-29，32.

[2]師超，仇洪冰，陳東華，等.一種簡單的分布式無線傳感器網(wǎng)絡(luò)時(shí)間同步方案[J].西安電子科技大學(xué)學(xué)報(bào)，2013，（1）：93-99，147.

[3]何劍海.無線傳感器網(wǎng)絡(luò)定位技術(shù)在農(nóng)田復(fù)雜環(huán)境中的應(yīng)用[J].無線互聯(lián)科技，2013，（2）：187-188.

[4]肖大威.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)存儲(chǔ)與訪問進(jìn)展分析[J].電子制作，2013，（9）：149.

（作者單位：北京郵電大學(xué)）