上傳人：q***

認(rèn)證信息

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

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

IP屬地：湖北

IP屬地：湖北 上傳時(shí)間：2024-02-29 格式：PPT 頁(yè)數(shù)：25 大?。?09.51KB 積分：30 舉報(bào) 版權(quán)申訴

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

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

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

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

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

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

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

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