【文章內容簡介】 。 協(xié)同通信示意圖協(xié)同通信CC(Cooperative Communication)：(a)節(jié)點在它的協(xié)作者，的幫助下與進行通信；(b)連接代表了協(xié)同通信。如果一個網(wǎng)絡的拓撲結構能夠建立起協(xié)同能量檢測，那當所有可能的直接鏈接和CC鏈接都是相通時候，文獻[20]保證有每一對節(jié)點之間的路徑的能源消耗是最低的，這將有利于網(wǎng)絡的拓撲結構的能量高效性。由于只考慮了單跳鄰居內協(xié)同通信節(jié)點。因此，協(xié)同通信的拓撲結構的CC鏈接只有單跳范圍內的連接，不是所有的鏈接都加入到了CC鏈接中。此外，對于每一對節(jié)點vi和vj，如果有多個CC鏈接，則只保持一個最小成本鏈接鏈路的連接。提出的兩個算法是貪婪算法。它們之間的主要區(qū)別是鏈接的處理順序。 第一種算法從原來的拓撲圖中貪婪地刪除鏈接(Deleting Links)，而第二算法從原來的拓撲圖中貪婪地添加鏈接(Adding Links). 兩種貪婪算法示意圖，圖(a)為建立于CC鏈接原始的拓撲圖，圖(b)(d)用第一種貪婪算法刪除鏈接，圖(e)和(f)用第二種算法增加鏈接。（7）文獻[21]提出一個分布式無死端（deadend free）拓撲維護協(xié)議（DFTM），能在激活節(jié)點數(shù)量最小化的條件下構建無死端網(wǎng)絡，并恢復已經(jīng)中斷的網(wǎng)絡通信。為了確保網(wǎng)絡中所有節(jié)點的能量消耗的均勻分布，DFTM提出了一個全局性的拓撲維護計劃，旨在執(zhí)行一個活動節(jié)點切換過程。在這過程中，所有當前活躍和休眠節(jié)點將每Tglobal秒轉變他們的模式到未定模式。然后匯聚節(jié)點隨機選擇一個節(jié)點作為初始節(jié)點來構建無死端的拓撲結構。選擇初始節(jié)點的隨機性使得每個節(jié)點成為活躍節(jié)點的概率都是相同的，也由此來達到功耗均勻分布的目的。 DFTM算法執(zhí)行過程。最初，所有的節(jié)??點都處于待定模式，即每個節(jié)點的最合適的模式尚未確定。過程開始時，隨機指定一個節(jié)點處于活躍狀態(tài)，這個節(jié)點轉換到狀態(tài)1，并被稱為初始節(jié)點。在狀態(tài)1中，所選擇的節(jié)點（初始節(jié)點）轉換到活躍模式并進入狀態(tài)2。初始節(jié)點隨后發(fā)出一條消息并搜索處于沒有休眠狀態(tài)的節(jié)點，然后轉換到狀態(tài)3接收回復。一旦未休眠的節(jié)點接收到了初始節(jié)點發(fā)出的消息，它就將自己的當前狀態(tài)回復給初始節(jié)點。而當初始節(jié)點的定時器到一定時間，則進入狀態(tài)圖4。初始節(jié)點首先將所有已回復的節(jié)點添加的其鄰居集（NS，neighbor set），然后將那些處于活躍模式節(jié)點添加到一個活躍的鄰居集（ANS，active neighbor set），并轉換到狀態(tài)5。初始節(jié)點從狀態(tài)5可能轉換到狀態(tài)6或者狀態(tài)7。如果節(jié)點處于ANS中且初始節(jié)點不滿足LDF條件，則初始節(jié)點的狀態(tài)轉換到狀態(tài)6。否則，轉換到狀態(tài)7。在狀態(tài)6，初始節(jié)點根據(jù)活躍節(jié)點選擇算法從NS節(jié)點中選擇一個新的活動節(jié)點，然后這個節(jié)點添加到其ANS中，并使該過程返回到狀態(tài)5，以驗證是否滿足的LDF條件。在狀態(tài)7，已被選擇的節(jié)點成為活躍節(jié)點，且被指定為新的初始節(jié)點。然后每個節(jié)點都使用其ANS執(zhí)行上述過程的拓撲構建。同時，由初始節(jié)點和其ANS中的節(jié)點的Voronoi多邊形的垂直平分線之間所包圍這些節(jié)點在進入睡眠模式。然后，該過程轉換到的最終狀態(tài)，即完成。在局部拓撲維護操作過程中，一些活動節(jié)點可能會突然因為節(jié)點碰撞，能量耗盡等原因而變得不可達。為了在節(jié)點故障時仍保持無死端的拓撲結構，DFTM采用本地拓撲維護操作，當活躍節(jié)點失效時以喚醒休眠節(jié)點。每個活躍節(jié)點都與處于活躍狀態(tài)的鄰居節(jié)點周期性地交換消息。當一個節(jié)點連續(xù)三次都未從一個特定的鄰居節(jié)點接收到確認消息，則將該鄰居節(jié)點從ANS中移除。通過仿真進行了一系列的數(shù)值模擬，將DFTM的性能與GAF、SPAN這些傳統(tǒng)的拓撲維護策略進行了比較。仿真結果顯示DFTM顯著減少了網(wǎng)絡中所需的激活節(jié)點數(shù)量，從而延長了網(wǎng)絡壽命。在大多數(shù)的模擬情景中，DFTM也成功地構建了一個無死端拓撲結構。另外，即使不知道傳感器的精確位置，DFTM仍然使得報文轉發(fā)時幾乎沒有“死端”現(xiàn)象的發(fā)生。（8）LEACH算法 lowenergy adaptive clustering hierarchy（LEACH）[22]算法是無線傳感器網(wǎng)絡中最早提出的一種自適應分簇拓撲算法。其后的大部分分簇拓撲控制算法都是基于它發(fā)展而來的。LEACH算法選舉簇頭的具體過程如下：每個節(jié)點產生一個介于0到1之間的隨機數(shù)，如果這個數(shù)小于閾值T(n)，則廣播消息通知其他所有節(jié)點自己是簇頭節(jié)點，其他節(jié)點則根據(jù)接收到的信號的強弱來決定加入哪個簇。在下一輪循環(huán)中，若節(jié)點已經(jīng)當選過簇頭，則設T(n)為0，這樣可以保證節(jié)點在之后的若干輪中不會再次當選為簇頭。T(n)可表示為：，nG 式21，其他其中：P是簇頭所在所有節(jié)點中所占的比率；r是選舉輪數(shù)；r mod(1/P)代表這一輪循環(huán)中當選過簇頭的節(jié)點個數(shù)；G是這一輪循環(huán)中從未當選過簇頭的節(jié)點集合。從的判決式中可以看出，當選過的簇頭節(jié)點在接下來的1/P輪循環(huán)中將不會再次當選簇頭。采用LEACH方法使因能量耗盡而失效的節(jié)點 呈隨機分布狀態(tài)，因而與一般靜態(tài)分簇算法相比，LEACH可以將網(wǎng)絡生命周期延長15%。但是LEACH假設所有的節(jié)點都能直接與終端節(jié)點通訊，采用連續(xù)數(shù)據(jù)發(fā)送模式和單跳模式，因此不適用監(jiān)測面積范圍大的應用，而且動態(tài)分簇帶來了額外的開銷。（9）PowerEfficient Gathering in Sensor Information Systems（PEGASIS）[23]算法是在LEACH算法的基礎上改進設計的。PEGASIS的基本思想是為了延長網(wǎng)絡的生命周期，節(jié)點只需要和它們最近的鄰居進行通信。節(jié)點與匯聚節(jié)點間的通信過程是輪流進行的，當所有節(jié)點都與匯聚點通信后，節(jié)點間再進行新一輪的輪流通信。由于這種輪流通信機制使得能量消耗能夠統(tǒng)一地分布到每個節(jié)點上，因此降低了整個傳輸所需消耗的能量。不同LEACH算法的多簇結構，PEGASIS算法在傳感器節(jié)點中采用鏈式結構進行連接。運行PEGASIS協(xié)議時，每個節(jié)點首先利用信號的強度來衡量其所有鄰居節(jié)點距離的遠近，在確定其最近鄰居的同時調整發(fā)送信號的強度以便只有這個鄰居能過聽到。其次，鏈上每個節(jié)點向鄰居發(fā)送和接收數(shù)據(jù)。采集到得數(shù)據(jù)以點對點方式傳送、融合、并最終被送到匯聚點。 PEGASIS算法鏈式結構圖PEFASIS協(xié)議的優(yōu)點是減少了LEACH在簇重構過程中所產生的開銷，并且通過數(shù)據(jù)融合降低了收發(fā)過程的次數(shù)，從而降低了能量的消耗，仿真結果表明，與LEACH協(xié)議相比，PEGASIS能夠提高網(wǎng)絡的生存周期近2倍。PEGASIS協(xié)議的缺點是：，而在實際情況中，傳感器節(jié)點一般需要采用多跳方式到達匯聚點。，因此節(jié)點很可能在同一時間內全部死亡。，但由于傳感器節(jié)點需要知道其鄰居的能量狀態(tài)信息以便傳輸數(shù)據(jù)，協(xié)議仍需要動態(tài)調整拓撲結構。對那些利用率較高的網(wǎng)絡而言，拓撲的調整會帶來更大的能源開銷。，遠距離的節(jié)點會引起過多的數(shù)據(jù)延遲，而且鏈首節(jié)點的唯一性使得鏈首成為瓶頸。 由Lindsey等人提出的分簇PEGASIS協(xié)議是對PEGASIS的擴展，該協(xié)議的目標是降低數(shù)據(jù)包到匯聚點傳送過程中所引起的延時。為此，協(xié)議采取了數(shù)據(jù)并行傳輸?shù)臋C制，并提出了兩種方法來避免傳輸期間的沖突和可能引起的信號干擾。第一種方法接了信號編碼方式，如碼分多址CDMA；第二種方法只允許空間上分隔的節(jié)點可以同時傳輸數(shù)據(jù)?；贑DMS的分簇PEGASIS協(xié)議采用樹狀分簇結構的方式，每一層選擇的節(jié)點向更高的一級的節(jié)點傳輸數(shù)據(jù)。協(xié)議要求在每個回合的數(shù)據(jù)采集過程中，給頂層的節(jié)點都想附近的鄰居發(fā)送數(shù)據(jù)，所有接收數(shù)據(jù)的節(jié)點被提升為上一層的節(jié)點。以此類推，最后頂層只有一個節(jié)點被保留下來并成為鏈首節(jié)點。為了使節(jié)點輪流與匯聚點間通信以均衡節(jié)點的能耗，第i回合的鏈首節(jié)點為節(jié)點號i除以節(jié)點總數(shù)N的余數(shù)。（10） Groupbased SEnsor Network（GSEN）[24]。在LEACH算法和PEGASIS算法的基礎上，文獻[24]結合這兩種算法的優(yōu)點提出了基于分簇的無線傳感器網(wǎng)絡算法GSEN（Groupbased Sensor Network）。在成簇階段，GSEN算法根據(jù)LEACH算法的方法將網(wǎng)絡中的節(jié)點分簇，簇內節(jié)點則根據(jù)PEGASIS中的貪婪算法組成相應的鏈，簇頭之間形成另一層次較高級的鏈，并從此鏈中選出一個簇頭節(jié)點和匯聚節(jié)點通信。在信息數(shù)據(jù)轉發(fā)階段，簇內節(jié)點沿著簇內鏈的方向將數(shù)據(jù)傳輸?shù)酱仡^，簇頭沿著另外的高級鏈將數(shù)據(jù)轉發(fā)至匯聚節(jié)點。與LEACH算法不同的是，GSEN并非每一輪都成簇和鏈，而是每五輪重新產生新的簇和鏈，但是每一輪都會選出一個新的簇頭節(jié)點。通過仿真分析發(fā)現(xiàn)，GSEN算法在40%節(jié)點死亡的情況下，數(shù)據(jù)轉發(fā)性能比LEACH高30%，比PEGASIS高30%。然后又提出了GSEN的改進算法（WCAGSEN），相比LEACH，它是利用增加簇頭權值的方法改進簇頭的選舉方法，在簇頭選舉過程中綜合考量節(jié)點的剩余能量、已擔任簇頭的次數(shù)和時間以及鄰居節(jié)點的節(jié)點度。仿真結果表明：WCAGSEN算法下的網(wǎng)絡中最后一個節(jié)點的死亡時間能夠比GSEN延長20%左右。 網(wǎng)絡壽命（生存時間）的定義網(wǎng)絡的生命周期的長短取決于生命周期到底是怎么樣定義的?，F(xiàn)在學術界，網(wǎng)絡的生命周期有著許多不同的定義。但是參閱較多拓撲控制算法，我們總結了幾種廣泛應用在不同拓撲控制算法的定義。（1）第一個節(jié)點的死亡時間：第一個節(jié)點的死亡時間常常用來定義網(wǎng)絡的生命周期[25]。 且這個死亡節(jié)點通常被稱為一個關鍵的節(jié)點。（2）存活節(jié)點的數(shù)量：活著節(jié)點的數(shù)量作為時間的函數(shù)的[26]，來衡量網(wǎng)絡的生命周期也有重要的意義[27]。較多的未死亡節(jié)點數(shù)目可以描述其網(wǎng)絡生命周期較長。（3）部分存活的節(jié)點：網(wǎng)絡的生命周期也可以是存活節(jié)點的時間函數(shù)[28]。只有節(jié)點的存活率低于某個閥值意味著網(wǎng)絡生命周期的結束。（4）少于建立骨干節(jié)點數(shù)目的時間：網(wǎng)絡生命周期指的是直到網(wǎng)絡缺乏骨干節(jié)點數(shù)目的時間[29]。在定義的網(wǎng)絡生命周期內，網(wǎng)絡拓撲主要有一組骨干節(jié)點形成，骨干節(jié)點的周期性循環(huán)可以延長網(wǎng)絡的生命周期。這種網(wǎng)絡生命周期的定義多用在層次型網(wǎng)絡拓撲。（5）部分連通支配集（CDS）節(jié)點的存活時間。這是適用于CDS拓撲控制技術的網(wǎng)絡生命周期的定義[30]。當存活的連通支配集（CDS）節(jié)點數(shù)目低于一個給定的閾值，意味著網(wǎng)絡生命周期到了盡頭。（6）數(shù)據(jù)包收發(fā)率大幅度下降的時間，此定義估算的是直到數(shù)據(jù)包傳送率急劇下降[31]的時間。網(wǎng)絡死亡時間t為當數(shù)據(jù)包收發(fā)率低于一個預定的閾值的時間。（7）保持連接到基站的節(jié)點的數(shù)目：網(wǎng)絡的存活程度由依舊能夠和基站通信的節(jié)點數(shù)目決定[32]。這種定義可以歸納為一個連通度的問題。 本章小結本章給出了無線傳感器網(wǎng)絡拓撲控制技術的定義。拓撲控制算法在無線傳感器網(wǎng)絡研究已經(jīng)有了較快發(fā)展，但是也面臨實際應用方面的挑戰(zhàn)；然后對無線傳感器網(wǎng)絡一些較新的拓撲控制算法做了介紹，最后對文獻中無線傳感器網(wǎng)絡的網(wǎng)絡壽命（生存時間）的定義進行了總結，為本文后續(xù)章節(jié)的相關拓撲控制算法的提出奠定了理論基礎。第3章　基于同心圓象限劃分的簇頭拓撲維護算法第3章 基于同心圓象限劃分的簇頭拓撲維護算法拓撲維護算法是在無線傳感器網(wǎng)絡拓撲初始構建完畢之后的小規(guī)?；謴途S護算法。本章提出了一種基于地理位置的，用同心圓象限劃分環(huán)弧空間的拓撲維護算法。在無線傳感器網(wǎng)絡中，為了獲取有效準確的監(jiān)測信息，網(wǎng)絡有時需要獲得地理信息，因此基于地理位置信息的拓撲控制、路由協(xié)議研究也廣泛起來。利用地理位置信息將網(wǎng)絡劃分成一重或多重的網(wǎng)格，網(wǎng)內節(jié)點按照從屬關系組織成一定的群組結構，并在此基礎上區(qū)分節(jié)點的職能，從而實現(xiàn)分層網(wǎng)絡拓撲結構以及分層路由協(xié)議，以改善網(wǎng)絡的性能?；诰W(wǎng)格劃分的典型拓撲控制算法有GAF算法、DAEA算法等；基于網(wǎng)格劃分的典型路由協(xié)議有：GRID[33]、GLS[34]算法等。還有一些學者將網(wǎng)格的概念用于WSN網(wǎng)絡的覆蓋和連通性的問題上[35]，也得到了很好的解決。GAF[36]（Geographical Adaptive Fidelity）算法是以節(jié)點地理位置為依據(jù)的分簇算法。該算法引入了虛擬單元格的思想，把監(jiān)測區(qū)域劃分成某干個虛擬單元格，將節(jié)點按照其地理位置信息劃入相應的單元格；在每個單元格中定期選舉產生一個簇頭，簇頭節(jié)點保持活動，其他節(jié)點進入睡眠狀態(tài)。 GAF算法中虛擬單元格劃分的示意圖GAF算法的第一階段是虛擬單元格的劃分。根據(jù)節(jié)點的位置信息和通信半徑，將整個網(wǎng)絡劃分成為若干個虛擬單元格，要求能保證相鄰單元格中的任意兩個節(jié)點之間能夠直接通信。假設所有節(jié)點的通信半徑為 R，網(wǎng)絡區(qū)域劃分為邊長為 r 的正方形虛擬單元格，為了保證相鄰兩個單元格內的任意兩個節(jié)點能夠直接通信，需要滿足如下關系式： 式31GAF算法的第二階段是簇頭節(jié)點的選擇。GAF算法中節(jié)點都有3種狀態(tài)：工作狀態(tài)、發(fā)現(xiàn)狀態(tài)和睡眠狀態(tài)。處于發(fā)現(xiàn)狀態(tài)的節(jié)點都可以競爭選簇頭。在每個單元格中，隨機產生一個簇頭節(jié)點，此節(jié)點處于工作狀態(tài)，其他節(jié)點周期性地進入睡眠或發(fā)現(xiàn)狀態(tài)。GAF算法中虛擬單元格劃分和節(jié)點狀態(tài)轉換機制具有一定的研究意義，但是要求節(jié)點精確的地理信息位置，對節(jié)點提出了很高的要求。四象限的空間結構是一種二維度的平面空間結構。而以原點為基準，橫軸、縱軸以及兩條經(jīng)過原點的X型直線將平面均分為8個象限，從原點的的右軸基準線開始，象限空間按逆時針方向劃分為8個子象限空間，再把同心圓嵌套到環(huán)弧空間里面，形成分扇區(qū)的環(huán)弧空間。根據(jù)基于地理位置的空間劃分的思想，我們提出一種基于同心圓象限的網(wǎng)格劃分方法。先根據(jù)四象限劃分思想，把平面劃分成類象限的2n（n=1,2,3……）部分，通過原點劃分象限的直線叫做象限分割線，然后再以原點為圓心，以不同半徑劃出同心圓，空間又被分為大小不同的圓弧。這樣，每個象限被不同半徑的圓弧劃分成若干個部分，每部分都由象限分割