上傳人：q***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：吳**（實名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2024-02-29 格式：PPT 頁數(shù)：25 大小：409.51KB 積分：30 舉報 版權(quán)申訴

第五章拓?fù)淇刂?.1概述WSN一般具有大規(guī)模、自組織、隨機部署、環(huán)境復(fù)雜、傳感器節(jié)點資源有限、網(wǎng)絡(luò)拓?fù)浣?jīng)常發(fā)生變化的特點[1]。這些特點使拓?fù)淇刂瞥蔀樘魬?zhàn)性研究課題。同時，這些特點也決定了拓?fù)淇刂圃赪SN研究中的重要性，其主要表現(xiàn)在以下幾個方面：（1）拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)；（2）拓?fù)淇刂票ＷC覆蓋質(zhì)量和連通質(zhì)量；（3）拓?fù)淇刂颇軌蚪档屯ㄐ鸥蓴_、提高M(jìn)AC(mediaaccesscontrol)協(xié)議和路由協(xié)議的效率、為數(shù)據(jù)融合提供拓?fù)浠A(chǔ)；（4）拓?fù)淇刂颇軌蛱岣呔W(wǎng)絡(luò)的可靠性、可擴展性等其他性能。總之，拓?fù)淇刂茖W(wǎng)絡(luò)性能具有重大的影響，因而對它的研究具有十分重要的意義第五章拓?fù)淇刂颇壳?，拓?fù)淇刂蒲芯恳呀?jīng)形成功率控制和睡眠調(diào)度兩個主流研究方向[14]。所謂功率控制，就是為傳感器節(jié)點選擇合適的發(fā)射功率；所謂睡眠調(diào)度，就是控制傳感器節(jié)點在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換。傳感器網(wǎng)絡(luò)拓?fù)淇梢愿鶕?jù)節(jié)點的可移動與否(動態(tài)的或靜態(tài)的)和部署的可控與否(可控的或不可控的)分為如下4類：（1）靜態(tài)節(jié)點、不可控部署：靜態(tài)節(jié)點隨機地部署到給定的區(qū)域。這是大部分拓?fù)淇刂蒲芯克鞯募僭O(shè)。對稀疏網(wǎng)絡(luò)的功率控制和對密集網(wǎng)絡(luò)的睡眠調(diào)度是兩種主要的拓?fù)淇刂萍夹g(shù)。（2）動態(tài)節(jié)點、不可控部署：這樣的系統(tǒng)稱為移動自組織網(wǎng)絡(luò)(mobileadhocnetwork，簡稱MANET)。其挑戰(zhàn)是無論獨立自治的節(jié)點如何運動，都要保證網(wǎng)絡(luò)的正常運轉(zhuǎn)。功率控制是主要的拓?fù)淇刂萍夹g(shù)。第五章拓?fù)淇刂疲?）靜態(tài)節(jié)點、可控部署：節(jié)點通過人或機器人部署到固定的位置。拓?fù)淇刂浦饕峭ㄟ^控制節(jié)點的位置來實現(xiàn)的，功率控制和睡眠調(diào)度雖然可以使用，但已經(jīng)是次要的了。（4）動態(tài)節(jié)點、可控部署：在這類網(wǎng)絡(luò)中，移動節(jié)點能夠相互定位。拓?fù)淇刂茩C制融入到移動和定位策略中。因為移動是主要的能量消耗，所以節(jié)點間的能量高效通信不再是首要問題。因為移動節(jié)點的部署不太可能是密集的，所以睡眠調(diào)度也不重要。第五章拓?fù)淇刂?.2拓?fù)淇刂圃O(shè)計目標(biāo)與研究現(xiàn)狀5.2.1拓?fù)淇刂频脑O(shè)計目標(biāo)1．覆蓋覆蓋可以看成是對傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的度量。在覆蓋問題中，最重要的因素是網(wǎng)絡(luò)對物理世界的感知能力[15]。覆蓋問題可以分為區(qū)域覆蓋、點覆蓋和柵欄覆蓋(barriercoverage)[16]。其中，區(qū)域覆蓋研究對目標(biāo)區(qū)域的覆蓋(監(jiān)測)問題；點覆蓋研究對一些離散的目標(biāo)點的覆蓋問題；柵欄覆蓋研究運動物體穿越網(wǎng)絡(luò)部署區(qū)域被發(fā)現(xiàn)的概率問題。相對而言，對區(qū)域覆蓋的研究較多。如果目標(biāo)區(qū)域中的任何一點都被k個傳感器節(jié)點監(jiān)測，就稱網(wǎng)絡(luò)是k-覆蓋的，或者稱網(wǎng)絡(luò)的覆蓋度為k。一般要求目標(biāo)區(qū)域的每一個點至少被一個節(jié)點監(jiān)測，即1-覆蓋。第五章拓?fù)淇刂埔驗橛懻撏耆采w一個目標(biāo)區(qū)域往往是困難的，所以有時也研究部分覆蓋，包括部分的1-覆蓋和部分的k-覆蓋。而且有時也討論漸近覆蓋，所謂漸近覆蓋是指，當(dāng)網(wǎng)絡(luò)中的節(jié)點數(shù)趨于無窮大時，完全覆蓋目標(biāo)區(qū)域的概率趨于1。對于已部署的靜態(tài)網(wǎng)絡(luò)，覆蓋控制主要是通過睡眠調(diào)度實現(xiàn)的。Voronoi圖是常用的覆蓋分析工具。對于動態(tài)網(wǎng)絡(luò)，可以利用節(jié)點的移動能力，在初始隨機部署后，根據(jù)網(wǎng)絡(luò)覆蓋的要求實現(xiàn)節(jié)點的重部署。虛擬勢場方法是一種重要的重部署方法。覆蓋控制是拓?fù)淇刂频幕締栴}。第五章拓?fù)淇刂?．連通傳感器網(wǎng)絡(luò)一般是大規(guī)模的，所以傳感器節(jié)點感知到的數(shù)據(jù)一般要以多跳的方式傳送到匯聚節(jié)點。這就要求拓?fù)淇刂票仨毐ＷC網(wǎng)絡(luò)的連通性。如果至少要去掉k個傳感器節(jié)點才能使網(wǎng)絡(luò)不連通，就稱網(wǎng)絡(luò)是k-連通的，或者稱網(wǎng)絡(luò)的連通度為k。拓?fù)淇刂埔话阋ＷC網(wǎng)絡(luò)是連通(1-連通)的。有些應(yīng)用可能要求網(wǎng)絡(luò)配置到指定的連通度。像漸近覆蓋一樣，有時也討論漸近意義下的連通，亦即當(dāng)部署區(qū)域趨于無窮大時，網(wǎng)絡(luò)連通的可能性趨于1。功率控制和睡眠調(diào)度都必須保證網(wǎng)絡(luò)的連通性，這是拓?fù)淇刂频幕疽蟆?．網(wǎng)絡(luò)生命期網(wǎng)絡(luò)生命期有多種定義。一般將網(wǎng)絡(luò)生命期定義為直到死亡節(jié)點的百分比低于某個閾值時的持續(xù)時間[17]。也可以通過對網(wǎng)絡(luò)的服務(wù)質(zhì)量的度量來定義網(wǎng)絡(luò)的生命期[18]，可以認(rèn)為網(wǎng)絡(luò)只有在滿足一定的覆蓋質(zhì)量、連通質(zhì)量、某個或某些其他服務(wù)質(zhì)量時才是存活的。功率控制和睡眠調(diào)度是延長網(wǎng)絡(luò)生命期的十分有效的技術(shù)。最大限度地延長網(wǎng)絡(luò)的生命期是一個十分復(fù)雜的問題，它一直是拓?fù)淇刂蒲芯康闹饕繕?biāo)。第五章拓?fù)淇刂?．吞吐能力設(shè)目標(biāo)區(qū)域是一個凸區(qū)域，每個節(jié)點的吞吐率為λbits/s，在理想情況下，則有下面的關(guān)系式[19]：

其中，A是目標(biāo)區(qū)域的面積，W是節(jié)點的最高傳輸速率，π是圓周率，Δ是大于0的常數(shù)，L是源節(jié)點到目的節(jié)點的平均距離，n是節(jié)點數(shù)，r是理想球狀無線電發(fā)射模型的發(fā)射半徑。由此可以看出，通過功率控制減小發(fā)射半徑和通過睡眠調(diào)度減小工作網(wǎng)絡(luò)的規(guī)模，在節(jié)省能量的同時，可以在一定程度上提高網(wǎng)絡(luò)的吞吐能力。5．干擾和競爭減小通信干擾、減少MAC層的競爭和延長網(wǎng)絡(luò)的生命期基本上是一致的。功率控制可以調(diào)節(jié)發(fā)射范圍，睡眠調(diào)度可以調(diào)節(jié)工作節(jié)點的數(shù)量。這些都能改變1跳鄰居節(jié)點的個數(shù)(也就是與它競爭信道的節(jié)點數(shù))。事實上，對于功率控制，網(wǎng)絡(luò)無線信道競爭區(qū)域的大小與節(jié)點的發(fā)射半徑r成正比[20]，所以減小r就可以減少競爭。睡眠調(diào)度顯然也可以通過使盡可能多的節(jié)點睡眠來減小干擾和減少競爭。第五章拓?fù)淇刂?．網(wǎng)絡(luò)延遲當(dāng)網(wǎng)絡(luò)負(fù)載較高時，低發(fā)射功率會帶來較小的端到端延遲；而在低負(fù)載情況下，低發(fā)射功率會帶來較大的端到端延遲[21]。對于這一點，一個直觀的解釋是：當(dāng)網(wǎng)絡(luò)負(fù)載較低時，高發(fā)射功率減少了源節(jié)點到目的節(jié)點的跳數(shù)，所以降低了端到端的延遲；當(dāng)網(wǎng)絡(luò)負(fù)載較高時，節(jié)點對信道的競爭是激烈的，低發(fā)射功率由于緩解了競爭而減小了網(wǎng)絡(luò)延遲。這是功率控制和網(wǎng)絡(luò)延遲之間的大致關(guān)系。7．拓?fù)湫再|(zhì)事實上，對于網(wǎng)絡(luò)拓?fù)涞膬?yōu)劣，很難直接根據(jù)拓?fù)淇刂频慕K極目標(biāo)給出定量的度量。因此，在設(shè)計拓?fù)淇刂?特別是功率控制)方案時，往往退而追求良好的拓?fù)湫再|(zhì)。除了連通性之外，對稱性、平面性、稀疏性、節(jié)點度的有界性、有限伸展性(spannerproperty)等，都是希望具有的性質(zhì)[22]。此外，拓?fù)淇刂七€要考慮諸如負(fù)載均衡、簡單性、可靠性、可擴展性等其他方面。拓?fù)淇刂频母鞣N設(shè)計目標(biāo)之間有著錯綜復(fù)雜的關(guān)系。對這些關(guān)系的研究也是拓?fù)淇刂蒲芯康闹匾獌?nèi)容。第五章拓?fù)淇刂?.2.2拓?fù)淇刂频难芯楷F(xiàn)狀當(dāng)前，拓?fù)淇刂频难芯恐饕宰畲笙薅鹊匮娱L網(wǎng)絡(luò)的生命期作為設(shè)計目標(biāo)，并集中于功率控制和睡眠調(diào)度兩個方面。下面分別予以介紹。各種拓?fù)淇刂扑惴ǖ谋容^見表5-1。第五章拓?fù)淇刂?．功率控制功率控制是一個十分復(fù)雜的問題。希臘佩特雷大學(xué)(UniversityofPatras)的Kirousis

等人將其簡化為發(fā)射范圍分配問題[23]，簡稱RA(rangeassignment)問題，并詳細(xì)討論了該問題的計算復(fù)雜性。設(shè)N={u1,…,un}是d(d=1,2,3)維空間中代表網(wǎng)絡(luò)節(jié)點位置的點的集合，r(ui)代表節(jié)點ui的發(fā)射半徑。RA問題就是要在保證網(wǎng)絡(luò)連通的前提下，使網(wǎng)絡(luò)的發(fā)射功率(各節(jié)點的發(fā)射功率的總和)最小，也就是要最小化，其中，是大于2的常數(shù)。在一維情況下，RA問題可以在多項式時間內(nèi)解決；然而在二維[12]和三維[11]情況下，RA問題是NP難的。實際的功率控制問題比RA問題更為復(fù)雜。這個結(jié)論從理論上告訴我們，試圖尋找功率控制問題的最優(yōu)解是不現(xiàn)實的，應(yīng)該從實際出發(fā)，尋找功率控制問題的實用解。針對這一問題，當(dāng)前已提出了一些解決方案，其基本思想都是通過降低發(fā)射功率來延長網(wǎng)絡(luò)的生命期。下面是幾個典型的解決方案，分別代表了目前功率控制的幾個典型的研究方向。第五章拓?fù)淇刂疲?）與路由協(xié)議結(jié)合的功率控制伊利諾斯大學(xué)的Narayanaswamy

等人提出并實現(xiàn)了一種簡單的將功率控制與路由協(xié)議相結(jié)合的解決方案COMPOW[20]。其基本思想是：所有的傳感器節(jié)點使用一致的發(fā)射功率，在保證網(wǎng)絡(luò)連通的前提下，將功率最小化。COMPOW建立各個功率層上的路由表，在功率層上，通過使用功率交換HELLO消息建立路由表，所有可達(dá)節(jié)點都是路由表中的表項。COMPOW選擇最小的發(fā)射功率，使得與具有相同數(shù)量的表項，其中，是最大發(fā)射功率。于是，整個網(wǎng)絡(luò)都使用公共的發(fā)射功率。在節(jié)點分布均勻的情況下，COMPOW具有較好的性能。但是，一個相對孤立的節(jié)點會導(dǎo)致所有的節(jié)點使用很大的發(fā)射功率，所以在節(jié)點分布不均的情況下，它的缺陷是明顯的。Kawadia

和Kumar提出的CLUSTERPOW[25]是對COMPOW的改進(jìn)。當(dāng)轉(zhuǎn)發(fā)一個包到目的節(jié)點d時，CLUSERPOW選擇出現(xiàn)d的最低層次的路由表，設(shè)為，然后，以功率而不是將其發(fā)送到下一跳節(jié)點。在CLUSTERPOW中，分簇是隱含的，且不需要任何簇頭節(jié)點，分簇通過給定功率層的可達(dá)性來實現(xiàn)，分簇的層次由功率的層次數(shù)來決定，分簇是動態(tài)的、分布的。CLUSTERPOW的主要缺陷是開銷太大。第五章拓?fù)淇刂疲?）基于節(jié)點度的功率控制具有代表性的基于節(jié)點度算法有柏林工業(yè)大學(xué)的Kubisch

等人提出的LMA和LMN[26]等?；诠?jié)點度算法的基本思想是：給定節(jié)點度的上限和下限，每個節(jié)點動態(tài)地調(diào)整自己的發(fā)射功率，使得節(jié)點的度數(shù)落在上限和下限之間。但是，基于節(jié)點度數(shù)的算法一般難以保證網(wǎng)絡(luò)的連通性。（3）基于方向的功率控制微軟亞洲研究院的Wattenhofer

和康奈爾大學(xué)的Li等人提出了一種能夠保證網(wǎng)絡(luò)連通性的基于方向的CBTC算法[27]。其基本思想是：節(jié)點選擇最小功率，使得在任何以為中心的角度為的錐形區(qū)域內(nèi)至少有一個鄰居。作者證明了當(dāng)時，可以保證網(wǎng)絡(luò)的連通性。麻省理工學(xué)院的Bahramgiri等人又將其推廣到三維空間，提出了容錯的CBTC[28]?；诜较虻乃惴ㄐ枰煽康姆较蛐畔?，因而需要很好地解決到達(dá)角度問題，節(jié)點需要配備多個有向天線，因而對傳感器節(jié)點提出了較高的要求。第五章拓?fù)淇刂疲?）基于鄰近圖的功率控制伊利諾斯大學(xué)的Li和Hou

提出的DRNG和DLMST[29]是兩個具有代表性的基于鄰近圖理論的算法。基于鄰近圖的功率控制算法的基本思想是：設(shè)所有節(jié)點都使用最大發(fā)射功率發(fā)射時形成的拓?fù)鋱D是G，按照一定的鄰居判別條件求出該圖的鄰近圖，每個節(jié)點以自己所鄰接的最遠(yuǎn)節(jié)點來確定發(fā)射功率。經(jīng)典的鄰近圖模型有RNG(relativeneighborhoodgraph)，GG(Gabrielgraph)，DG(Delaunaygraph)，YG(Yaograph)和MST(minimumspanningtree)等。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能夠保證網(wǎng)絡(luò)的連通性，在平均功率和節(jié)點度等方面具有較好的性能?；卩徑鼒D的功率控制一般需要精確的位置信息。此外，微軟亞洲研究院的Wattenhofer等人提出的XTC[30]算法對傳感器節(jié)點沒有太高的要求，對部署環(huán)境也沒有過強的假設(shè)，提供了一個面向簡單、實用的研究方向。因為XTC代表了功率控制的發(fā)展趨勢，本章將詳細(xì)加以介紹。第五章拓?fù)淇刂?．睡眠調(diào)度功率控制通過降低節(jié)點的發(fā)射功率來延長網(wǎng)絡(luò)的生存時間，但卻沒有考慮空閑偵聽時的能量消耗和覆蓋冗余。事實上，無線通信模塊在空閑偵聽時的能量消耗與收發(fā)狀態(tài)時相當(dāng)，覆蓋冗余也造成了很大的能量浪費。所以，只有使節(jié)點進(jìn)入睡眠狀態(tài)，才能大幅度地降低網(wǎng)絡(luò)的能量消耗。這對于節(jié)點密集型和事件驅(qū)動型的網(wǎng)絡(luò)十分有效。如果網(wǎng)絡(luò)中的節(jié)點都具有相同的功能，扮演相同的角色，就稱網(wǎng)絡(luò)是非層次的或平面的，否則就稱為是層次型的。層次型網(wǎng)絡(luò)通常又稱為基于簇的網(wǎng)絡(luò)。下面分別介紹非層次網(wǎng)絡(luò)和層次型網(wǎng)絡(luò)的具有代表性的睡眠調(diào)度算法。第五章拓?fù)淇刂疲?）非層次型網(wǎng)絡(luò)的睡眠調(diào)度算法非層次型睡眠調(diào)度的基本思想是：每個節(jié)點根據(jù)自己所能獲得的信息，獨立地控制自己在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換。它與層次型睡眠調(diào)度的主要區(qū)別在于：每個節(jié)點都不隸屬于某個簇，因而不受簇頭節(jié)點的控制和影響。（2）層次型網(wǎng)絡(luò)的睡眠調(diào)度算法層次型網(wǎng)絡(luò)睡眠調(diào)度的基本思想是：由簇頭節(jié)點組成骨干網(wǎng)絡(luò)，則其他節(jié)點就可以(當(dāng)然未必)進(jìn)入睡眠狀態(tài)。層次型網(wǎng)絡(luò)睡眠調(diào)度的關(guān)鍵技術(shù)是分簇。第五章拓?fù)淇刂?.3拓?fù)淠Ｐ团c拓?fù)淇刂扑惴?.3.1拓?fù)淠Ｐ碗S機圖理論在信息科學(xué)中被廣泛地應(yīng)用，UDG、RNG和MST等都是基于隨機圖理論的經(jīng)典拓?fù)淠Ｐ?，很多的拓?fù)浣Y(jié)構(gòu)都是在它們的基礎(chǔ)上演變而來的。從連通和抗干擾的角度對拓?fù)淠Ｐ瓦M(jìn)行分類，如圖5-1所示。第五章拓?fù)淇刂?．單位圓圖(UDG)假定網(wǎng)絡(luò)中N個節(jié)點構(gòu)成了二維平面中的節(jié)點集V，所有節(jié)點都以最大功率工作時所生成的拓?fù)浞Q為UDG(unitdiskgraph)。若所有節(jié)點最大的傳輸范圍為1，無線節(jié)點在平面中就構(gòu)成了一個UDG，當(dāng)且僅當(dāng)圖中每對節(jié)點間的歐氏距離dis(u,v)≤1時，兩個節(jié)點之間才有鏈路相連。UDG的連通性是網(wǎng)絡(luò)能夠提供的最大連通性，因此，任何拓?fù)淇刂扑惴ㄉ傻耐負(fù)涠际荱DG的子圖[48]。2．準(zhǔn)規(guī)則單位圓圖(QUDG)假設(shè)V、R是兩個空間平面的節(jié)點集，且，設(shè)參數(shù)d∈[0，1]，則對稱的歐氏圖(V，E)被稱為以d為參數(shù)的準(zhǔn)規(guī)則單位圓圖(QUDG)。圖中對任意α，β∈V，若|αβ|≤d，則(α，β)∈E；若|αβ|>1，則(α，β)|E。在實際應(yīng)用中，節(jié)點的發(fā)射功率會因為硬件或環(huán)境等各種原因而變化，所以QUDG是比UDG更接近實際的拓?fù)淠Ｐ蚚8]。未經(jīng)拓?fù)淇刂扑惴ㄌ幚淼腢DG是非平坦的，非平坦圖邊的非頂點交叉現(xiàn)象將給信道帶來干擾。為了對其作平面化處理，簡化拓?fù)浣Y(jié)構(gòu)，許多UDG的近似子圖算法被提了出來[5]。其中最具代表性的有Gabriel圖(GG)、相關(guān)鄰近圖(RNG)和最小生成樹(MST)。第五章拓?fù)淇刂?．Gabriel圖(GG)在二維歐氏空間中，V為節(jié)點集，w,u,v∈V，w≠u≠v。連接GG中任意兩個節(jié)點u和v，則以邊d(u,v)為直徑、通過節(jié)點u和v的圓內(nèi)不包含其他任何節(jié)點。如果(dis(u,v))2≤min((dis(w,u))2+(dis(w,v))2),w≠u≠v，則說明d(u,v)為GG的一條邊。在傳輸功率正比傳輸距離的平方時，GG是最節(jié)能的拓?fù)淠Ｐ汀?．相關(guān)鄰近圖(RNG)在二維歐氏空間中，V為節(jié)點集，任意兩個節(jié)點間的邊長小于或等于u、v分別與其他任意一節(jié)點的距離的最大值，即歐氏距離dis(u,v)≤max(dis(w,u),dis(w,v))，w,u,v∈V，w≠u≠v。若d(u,v)為RNG的一條邊，則在分別以點u或v為圓心，以dis(u,v)為半徑的兩個圓R1和R2的交集I內(nèi)不能有其他節(jié)點[6]，如圖2所示。RNG是由GG產(chǎn)生的，RNG稀疏程度和連通性均介于MST與GG之間，優(yōu)于MST，且沖突干擾優(yōu)于GG，易于用分布式算法構(gòu)造。第五章拓?fù)淇刂?．最小生成樹(MST)MST是保持圖連接所需的滿足最小權(quán)值的鏈路子集。MST是RNG的子圖，其特征是連通但不形成回路，任意兩個節(jié)點均可以相互通信。每個節(jié)點出現(xiàn)在樹上，鏈路總長度最小。構(gòu)造MST有兩種主要算法，即Kruskal和Prim算法。Kruskal算法總是選擇剩余權(quán)值最小的邊加入最小生成樹；Prim算法則通過任意將節(jié)點加入最小生成樹，同時僅將權(quán)值更小的邊加入。6．其他常用的拓?fù)淠Ｐ统松厦嬗懻撨^的幾種模型外，Yao圖(YG)、Voronoitessellation(VT)和Delaunaytriangulation(DT)也是常用的模型。YG分很多扇區(qū)，節(jié)點在扇區(qū)內(nèi)選擇最近的鄰居進(jìn)行通信，具有簡單的分布式結(jié)構(gòu)，節(jié)點的度較高；VT首先識別網(wǎng)絡(luò)冗余節(jié)點，然后計算出可被關(guān)閉的冗余節(jié)點，最后由工作節(jié)點構(gòu)建覆蓋集；DT中點集V的一個三角剖分T只包含Delaunay邊，具有最大化最小角、惟一性(任意四點不能共圓)等特性。第五章拓?fù)淇刂?.3.2拓?fù)淇刂扑惴?．平面網(wǎng)絡(luò)中的拓?fù)淇刂啤β士刂圃谄矫婢W(wǎng)絡(luò)中，所有的節(jié)點都是同構(gòu)的，具有同樣的硬件、同樣的能力，完成同樣的任務(wù)。在平面網(wǎng)絡(luò)中拓?fù)淇刂谱罨镜姆椒ㄊ强刂婆c一個節(jié)點通信的鄰節(jié)點集。而這個問題與控制節(jié)點的發(fā)射功率有著密切的關(guān)系，所以一般稱為功率控制。目前，對平面網(wǎng)絡(luò)的拓?fù)淇刂蒲芯糠椒ㄖ饕譃閮深悾篴)概率分析的方法，在節(jié)點按照某種概率密度分布的情況下，計算使拓?fù)錆M足某些性質(zhì)(一般是連通性、覆蓋率)所需要的最小發(fā)射功率和最小鄰節(jié)點個數(shù)；b)計算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)拓?fù)?，以滿足某些性質(zhì)。第五章拓?fù)淇刂疲?）概率分析方法一種基于幾何隨機圖的類似算法；k-連通問題；將鄰節(jié)點數(shù)控制在一定數(shù)量內(nèi)的分布式算法；關(guān)于節(jié)點有不同最大發(fā)射范圍的問題；功率控制和移動性的關(guān)系。（2）計算幾何方法最小生成樹(MST)；Gabriel圖(Gabrielgraph,GG)；相關(guān)鄰近圖(relativeneighborgraph,RNG)；DRNG和DLMST是兩個具有代表性的基于鄰近圖理論的算法；分布式公共功率協(xié)議COMPOW[61]，K-NEIGH協(xié)議[62]、XTC、CCP和SPAN等。第五章拓?fù)淇刂?．層次型網(wǎng)絡(luò)中的拓?fù)淇刂平Y(jié)構(gòu)研究無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的另一種方法是在網(wǎng)絡(luò)節(jié)點中形成一種層次關(guān)系，構(gòu)成一個層次型的網(wǎng)絡(luò)。目前主要有兩種研究手段，即采用支配集的層次型網(wǎng)絡(luò)和采用分簇結(jié)構(gòu)的層次型網(wǎng)絡(luò)。（1）采用支配集的層次型網(wǎng)絡(luò)文獻(xiàn)[66]介紹了兩種集中式的例子。a)生成樹結(jié)構(gòu)；b)先構(gòu)造一個不一定連通的支配集，然后在下一個階段，把集合內(nèi)的所有節(jié)點連接在一起。TopDisc算法中提出了兩種具體的節(jié)點狀態(tài)標(biāo)記辦法，分別稱為三色算法和四色算法。（2）采用簇結(jié)構(gòu)的層次