【正文】 內(nèi)的節(jié)點就近按照環(huán)弧空間劃分 的情況就近加入剛才已找到的簇頭。該算法是按照同心圓和象限空間的方法劃分出的環(huán)弧空間。本文主要考 慮的就是無線傳感器網(wǎng)絡(luò)拓?fù)渚S護階段的拓?fù)淇刂扑惴?—— 在簇頭節(jié)點失效之后，如何維護網(wǎng)絡(luò)性能以及恢復(fù)通信，延長系統(tǒng)生存時間。拓?fù)淇刂频闹饕康氖莾?yōu)化網(wǎng)絡(luò)性能，減少節(jié)點能耗，延長網(wǎng)絡(luò)生命期，同時具有保證連通度和覆蓋度、減少通信干擾、提高通信效率以及增強網(wǎng)絡(luò)的健壯性等作用。（保密的學(xué)位論文在解密后遵守此規(guī)定） 學(xué)位論文作者簽名： 簽字日期： 年 月 日 導(dǎo) 師 簽 名： 簽字日期： 年 月 日 摘 要 II 摘 要 無線傳感器網(wǎng)絡(luò)（ WSN， wireless sensor work）是由眾多能量有限的無線傳感器節(jié)點組成的，通過節(jié)點感知和 采集監(jiān)測范圍內(nèi)的相關(guān)目標(biāo)信息，用無線通信方式發(fā)送和接收數(shù)據(jù)、自適應(yīng)的網(wǎng)絡(luò)系統(tǒng)。 論文作者簽名： 簽字日期： 年 月 日 關(guān)于論文使用授權(quán)的說明 學(xué)位論文作者完全了解 XX 有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬 XX 大學(xué)。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明。 碩 士 學(xué) 位 論 文 基于分簇的無線傳感器網(wǎng)絡(luò)拓?fù)渚S護算法研究 Research of Topology Maintenance Algorithm for Wireless Sensor Network Based on Clustering 二零一三年四月 分類號： UDC： 密 級： 公開 保密年限： 年 基于分簇的無線傳感器網(wǎng)絡(luò)拓?fù)渚S護算法研究 Research of Topology Maintenance Algorithm for Wireless Sensor Network Based on Clustering 學(xué)科門類： 學(xué)科專業(yè)： 論文作者： 指導(dǎo)教師： 培養(yǎng)單位： 聲 明 I 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論 文，是本人在導(dǎo)師的指導(dǎo)下，獨立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)校有權(quán)保留并向國家有關(guān)部門或機構(gòu) 送交論文的復(fù)印件和電子版，允許學(xué)位論文被查閱和借閱；學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存、匯編學(xué)位論文。 拓?fù)淇刂萍夹g(shù) (topology control technology)是無線傳感器網(wǎng)絡(luò)的重要支撐技術(shù)和研究領(lǐng)域的熱點、難點。傳統(tǒng)的拓?fù)淇刂扑惴ㄖ饕紤]到拓?fù)錁?gòu)建階段的拓?fù)?，較少考慮到拓?fù)渚S護階段的拓?fù)淇刂茊栴}，即節(jié)點發(fā)生異變后，整個網(wǎng)絡(luò)體系是否能夠依照原拓?fù)淇刂扑惴ɡ^續(xù)工作。 根據(jù) GAF（ Geographical Adaptive Fidelity）算法提出了一種基于同心圓的環(huán)分象限空間的簇頭拓?fù)渚S護算法。假設(shè)網(wǎng)絡(luò)的初始拓?fù)錁?gòu)建完成，所有節(jié)點都被分簇并且有簇頭，然后所有簇頭按照同心圓和區(qū)域象限的方法劃分的網(wǎng)格環(huán)，尋找匯聚節(jié)點方向上的離自己最近的簇頭節(jié)點。該算法維護了原有的網(wǎng)絡(luò)屬性，保證了簇頭節(jié)點與匯聚節(jié)點的連通性，延長了網(wǎng)絡(luò)的生存時間。該算法基于路徑距離模型和能量消耗模型，通過簇頭節(jié)點與匯聚節(jié)點通信時數(shù)據(jù)轉(zhuǎn)發(fā)的最佳跳數(shù)的轉(zhuǎn)發(fā)，使數(shù)據(jù)通信消耗的能量最低，從而減少了節(jié)點能耗，具有較好的能量有效性。 topology control。 energy efficiency。 致 謝 ................................................................................................... 51 第 1 章 緒論 1 第 1 章 緒論 課題的 研究背景 、目的及意義 信息的獲取和處理是人類認(rèn)識世界的兩個重要方面?？萍嫉倪M步，使人類的許多想法成為可能， 計算機系統(tǒng)的出現(xiàn)增強了人類處理信息的能力 , 而無線傳感器網(wǎng)絡(luò)則大大拓展了人類獲取信息的能力 。 無線傳感器網(wǎng)絡(luò)集成了許多目前最新的研究成果，比如傳感器節(jié)點用到的微機電系統(tǒng)和嵌入式系統(tǒng)開發(fā)技術(shù)，信息傳輸階段用到的分布式信息處理技術(shù)和以 ，這些應(yīng)用于無線傳感器網(wǎng) 絡(luò)的諸多技術(shù)都是各自領(lǐng)域的最新成果。 無線傳感器網(wǎng)絡(luò)（ WSN， wireless sensor work） 是 一種特殊的 Ad hoc 網(wǎng)絡(luò)，由部署在監(jiān)測區(qū)域內(nèi)大量的低成本、體積小、多功能的傳感器節(jié)點通過自組織方式組成 ，通過無線通信方式形成一種多跳的、自組織的網(wǎng)絡(luò) 。 無線 傳感器網(wǎng)絡(luò) 系統(tǒng) 具有 成本低、 易部署、自組織、 管理方便 、可靠性 高等特點，使其在國防軍事、環(huán)境監(jiān)測和預(yù)報、交通管理、智能家居、建筑物狀態(tài)監(jiān)控、醫(yī)療衛(wèi)生、制造業(yè)、工農(nóng)業(yè)控制等諸多領(lǐng)域有著廣闊的應(yīng)用前景和很高的應(yīng)用價值。美國商業(yè)周刊和 MIT技術(shù)評論在預(yù)測未來技術(shù)發(fā)展報告中，分別將無線傳感器網(wǎng)絡(luò)列為 21世紀(jì)最有影響力的 21項技術(shù)和改變世界的 10大技術(shù)之一 [12]。 2021 年，歐洲第 1 屆專業(yè)傳感器網(wǎng)絡(luò)會議在德國柏林召開。 我國頒布的《國家中長期科學(xué)與技術(shù)發(fā)展規(guī)劃綱要（ 2021年 2020年）》 [4]中，為信息領(lǐng)域確定了三個前沿方向，其中智能感知技術(shù)和自組織網(wǎng)絡(luò)技術(shù)都直接與 WSN的研究相關(guān)。 無線傳感器網(wǎng)絡(luò)巨大應(yīng)用前景為科學(xué)研究者們帶來了一個新的研究方向，提出了新的技術(shù)挑戰(zhàn)。其中拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)的一項關(guān)鍵技術(shù)，拓?fù)淇刂?技術(shù) 對網(wǎng)絡(luò)的 其他 性能有著很大的影響 ，同時， 拓?fù)淇刂萍夹g(shù)也是無線傳感器網(wǎng)絡(luò) 領(lǐng)域 許多其他 相關(guān) 研究課題的支撐技術(shù)之一。通過此算法，可以以較小的開銷恢復(fù)中斷的節(jié)點通信 和網(wǎng)絡(luò)通信，有效的提高網(wǎng)絡(luò)通信質(zhì)量、減小傳輸延時，保證數(shù)據(jù)成功發(fā)送率的情況下，減小能量的損耗 。 課題的研究現(xiàn)狀 由于無線傳感器網(wǎng)絡(luò)自身節(jié)點攜帶能量有限、網(wǎng)絡(luò)拓?fù)湟鬃兓㈦S機部署、通信 環(huán)境復(fù)雜等特點決定了拓?fù)淇刂萍夹g(shù)在無線傳感器網(wǎng)絡(luò)中的重要性。以麻省理工學(xué)院，加州大學(xué)伯克利分校，加州大學(xué)洛杉磯分校，伊利諾斯大學(xué)為代表的國外著名第 1 章 緒論 3 高校，在無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯糠矫嬉呀?jīng)取得了初步的研究成果。 隨著無線傳感器網(wǎng)絡(luò)應(yīng)用的進一步深入，拓?fù)淇刂萍夹g(shù)也應(yīng)該進行下一步的研究。拓?fù)錁?gòu)建指的是網(wǎng)絡(luò)拓?fù)涑跏蓟峭負(fù)鋸臒o到有的過程，拓?fù)渚S護指的是網(wǎng)絡(luò)拓?fù)浣⒑螅瑑?yōu)化網(wǎng)絡(luò)拓?fù)?，是拓?fù)鋸挠械胶玫倪^程。但是拓?fù)渚S護作為組成拓?fù)淇刂频膬蓚€子環(huán)節(jié)之一，且拓?fù)渚S護是銜接于初始拓?fù)涞暮罄m(xù)發(fā)展，這些都足以說明拓?fù)渚S護對于網(wǎng)絡(luò)的整個拓?fù)淇刂频慕⒂兄种匾囊饬x。目前的拓?fù)淇刂频难芯恳讶〉昧?較大進展，提出了許多經(jīng)典算法，現(xiàn)有的拓?fù)淇刂拼蟛糠盅芯慷际墙⒃谶@些經(jīng)典算法之上。但是，目前拓?fù)渚S護算法的研究還很不充分，特別是針對拓?fù)淇刂频耐負(fù)渚S護算法，還需要做大量的相關(guān)研究。無線傳感器網(wǎng)絡(luò)典型的體系結(jié)構(gòu)如圖 所示。傳感器節(jié)點采集到的數(shù)據(jù)在傳遞過程中可能被多個節(jié)點的處理， 并直接或者間接 傳遞到 BS 節(jié)點，最后通過外部網(wǎng)絡(luò)如衛(wèi)星、互聯(lián)網(wǎng)或者移動通信網(wǎng)絡(luò)等方式傳遞給管理中心。傳感器節(jié)點 又 擔(dān)當(dāng)著終端和路由的雙重角色，除了監(jiān)測、采集和處理監(jiān)測對象的信息數(shù)據(jù)外，還可能要負(fù)責(zé)對其他節(jié)點傳遞來的數(shù)據(jù) 進行轉(zhuǎn)發(fā)、 信息融合、存儲等功能。依據(jù)特殊要求， 傳感器 節(jié)點還可能包括定位、能量補給或移動等模塊。目前，無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)主要有：定位技術(shù)、拓?fù)淇刂萍夹g(shù)、數(shù)據(jù)融合 技術(shù) 、路由協(xié)議、網(wǎng)絡(luò)安全、適用于無線傳感器網(wǎng)絡(luò)的軟件或者硬件設(shè)計等。傳感器節(jié)點一般是由人工或者機械隨機撒布在監(jiān)測區(qū)域內(nèi)的，所以其位置是未知的。節(jié)點只有明確自身的位置才能向管理者準(zhǔn)確傳遞信息詳細(xì)說明 “在什么區(qū)域發(fā)生了什么事件 ”。而人工在確定 無線傳感器網(wǎng)絡(luò)的位置 或者給節(jié)點安裝 GPS等節(jié)點位置 接收器會受到成本、功耗、 可 擴展性 、復(fù)雜度 等問題的限制，在某些 場合可能無法實現(xiàn)，所以采取一定的 方法 機制或者算法實現(xiàn)節(jié)點定位是必要的。它是解決網(wǎng)絡(luò)連通性、提高連通可靠性、增強容錯性以及節(jié)省能耗的最有效方法之一。數(shù)據(jù)融合技術(shù)還可以減少傳輸?shù)臄?shù)據(jù)量，達到節(jié)約能耗的目的。 （ 4） 路由協(xié)議 能耗問題是無線傳感器網(wǎng)絡(luò)設(shè)計考慮的重點，其很多特性決定了傳統(tǒng)無線網(wǎng)絡(luò)的路由協(xié)議在無線傳感器網(wǎng)絡(luò)中是不適用的。因此，路由協(xié)議問題也是無線傳感器網(wǎng)絡(luò)的熱點問題之一。 （ 5） 網(wǎng)絡(luò)安全 無線傳感器網(wǎng)絡(luò)是通過無線 通信 信道進行數(shù)據(jù) 發(fā)送轉(zhuǎn)發(fā)接收 的，因此網(wǎng)絡(luò)安全問題是一個非常重要的問題。為了保證任務(wù)的機密布置和任務(wù)執(zhí)行結(jié)果的安全傳遞和融合 ， 無線傳感器網(wǎng)絡(luò)需要實現(xiàn)一些最基本的安全機制 ：如 數(shù)據(jù)加 密 特 性 ， 點到點的消息認(rèn)證、完整性鑒別、新鮮性 ，數(shù)據(jù) 認(rèn)證廣播以及安全管理 [12]。對于研究者來說，徹底解決所有問題是很難實現(xiàn)的，應(yīng)該針對某個或者某些特定條件或問題進行研究，改善無線傳感器網(wǎng)絡(luò)性能。 無線傳感器網(wǎng)絡(luò)在云南省跨境區(qū)域的應(yīng)用 無線傳感器網(wǎng)絡(luò)（ wireless sensor works, WSN）是近十年來發(fā)展迅速的一種新型網(wǎng)絡(luò)體系，由于其布置靈活、自組織、成本低廉、實時性強、免維護等特點，在工業(yè)控制、環(huán)境監(jiān)測、減災(zāi)防災(zāi)、物流、醫(yī)療、國防等領(lǐng)域得到了廣泛的應(yīng)用，學(xué)術(shù)界對其體系結(jié) 構(gòu)、通信協(xié)議、電路設(shè)計、操作系統(tǒng)等關(guān)鍵技術(shù)的研究升溫。 云南省跨境地區(qū)的生態(tài)環(huán)境有四個重要特征：（一）信息量巨大。（二）空間信息上的多尺度和屬性信息上的多層面疊置特征。 在屬性信息方面，該地帶存在著從大氣 植被 水域 土壤 地質(zhì)體等多層面的屬性疊加特征。（四）該地帶生態(tài)環(huán)境各要素之間相互關(guān)聯(lián)，往往互為因果，錯綜復(fù)雜 [13]。一個網(wǎng)絡(luò)拓?fù)湟约巴?撲機制對網(wǎng)絡(luò)的影響是非常大的，對于大規(guī)模網(wǎng)絡(luò)的拓?fù)溲芯坑兄匾囊饬x。所以，跨境地區(qū)的復(fù)雜地形和復(fù)雜電磁環(huán)境，非常容易 導(dǎo)致網(wǎng)絡(luò)的拓?fù)浒l(fā)生變化， 如網(wǎng)絡(luò)中某個或者某些節(jié)點的通訊受到干擾或者破壞進而不能響應(yīng)通信時， 如何 恢復(fù)拓?fù)?或者重建新的拓?fù)洳⒒謴?fù)網(wǎng)絡(luò)通信 顯得尤為重要。然后有針對性的 研究 了無線傳感器網(wǎng)絡(luò) 拓?fù)淇刂萍夹g(shù) ， 以拓?fù)渚S護作為拓?fù)淇刂萍夹g(shù)的主要切入點，提出了層次型拓?fù)淇刂萍夹g(shù)中簇頭失效的解決方案。 （ 2） 根據(jù)地理位置的網(wǎng)格劃分思想，提出用同心圓和象限劃分的環(huán)弧空間XX 大學(xué)碩士學(xué)位論文 8 的簇頭拓?fù)渚S護算法。 （ 4） 分別對提 出的算法進行了理論分析和模擬仿真數(shù)據(jù)上的比較分析，得出相應(yīng)的結(jié)論 。主要介紹了無線傳感網(wǎng)絡(luò)的概念、特點，特別針對無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)、節(jié)點結(jié)構(gòu)以及無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)和國內(nèi)外無線傳感器網(wǎng)絡(luò)典型應(yīng)用做了較詳細(xì)的介紹。 第三章， 提出基于同心圓和區(qū)域象限劃分環(huán)弧空間的簇頭拓?fù)渚S護算法。 第四章， 提出基于多跳中繼轉(zhuǎn)發(fā)的簇頭拓?fù)渚S護算法 。 第五章， 對全文的工作進行了回顧和總結(jié)，對未來的研究工作進行了展望。一般來說網(wǎng)絡(luò)拓?fù)浒ㄒ韵缕叻N方式：點對點型、總線型、星型、環(huán)型、 Mesh 型、樹型、鏈狀、混合型 。 拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)通信和組網(wǎng)的基礎(chǔ)，其性能的好壞將直接或者間接影響無線傳感器網(wǎng)絡(luò)其他方面。 （ 2） 保證網(wǎng)絡(luò)的連通度和覆蓋率 無線傳感器網(wǎng)絡(luò)的連通覆蓋是反應(yīng)網(wǎng)絡(luò)的服務(wù)質(zhì)量和服務(wù)能力的兩個重要指標(biāo) 。連通是拓?fù)淇刂频幕疽螅淇梢员ＷC數(shù)據(jù)傳輸?shù)目煽啃浴? （ 3） 減少通信干擾，提高通信效率 一般來說，為了有效地監(jiān)測目標(biāo)場景對象，布置于監(jiān)測環(huán)境中的傳感器節(jié)點的密度較大。因此，需要通過拓?fù)淇刂萍夹g(shù)的功率控制來解決這一問題。拓?fù)淇刂拼_定網(wǎng)絡(luò)中節(jié)點之間的關(guān)系及節(jié)點分擔(dān)的角色，對數(shù)據(jù)進行轉(zhuǎn)發(fā)，為路由協(xié)議奠定基礎(chǔ)。為傳感器網(wǎng)絡(luò)選擇合適的節(jié)點對采集來的監(jiān)測數(shù)據(jù)進行處理并發(fā)給管理者是拓?fù)淇刂萍夹g(shù)另一工作，可以減少網(wǎng)絡(luò)不必要的開銷和降低通信量。 由此可見，無線傳感器網(wǎng)絡(luò)拓?fù)淇刂萍夹g(shù)在無線傳感器網(wǎng)絡(luò)研究領(lǐng)域具有十分重要的研究意義。大部分平面拓?fù)浣Y(jié)構(gòu)又基于節(jié)點的功率控制，所謂功率控制，就是為無線傳感器網(wǎng)絡(luò)的節(jié)點選擇合適的發(fā)射功率和接收功率，即節(jié)點的 發(fā)送功率和接收功率時可調(diào)的。在層次型拓?fù)淇刂频难芯糠较?，主要?LEACH 和 HEED 成簇算法，也有 TopDisc 和 GAF 分簇算法。 第 2 章 無線傳感器網(wǎng)絡(luò)拓?fù)淇刂萍夹g(shù)概述 11 （ 1） S. Chen[15]等人研究了一種可預(yù)測（其隨時間演進的網(wǎng)絡(luò)拓?fù)淇梢员煌评砘蛘哳A(yù)測） 的 DTN（ de