無線AdHoc網(wǎng)絡連通性分析

1、abstractwireless ad hoc network is a selforganized mobile network, compared with the traditional cellular networks, it is formed without the aid of fixed infrastructure. due to its flexibility and high survivability, it is widely used in military, civilian and commercial areas. the connectivity of a

2、d hoc network is critical for its topology is dynamic. besides, connectivity is a prerequisite for ad hoc network and it is the foundation for the design of the higher layer. this thesis studies the connectivity of ad hoc network and analysises the factors that affect connectivity based on stochasti

3、c geometryfirstly, bi-connectivity in one and two dimensional ad hoc network is investigated. for the one-dimensional case, the basic conditions for bi-connectivity are discussed from the viewpoint of the probability and the closed formula for bi-connectivity probability is derived. then for the two

4、 dimensional network, based on the mobility of the nodes in ad hoc network, a node moving algorithm improving the effectiveness of the link is studied this algorithm changes the network from 1-connectivity to bi-connectivity and enhances the network connectivity and invulnerability.secondly, the con

5、nectivity based on fading channels is analyzed. according to poisson point process, the network model is set up. with rayleigh fading channels, a sir model is used to calculate the probability of being no isolated node and then the network connectivity probability is obtained thirdly, the effects of

6、 interference in ad hoc network are studied. based on shot-noise theory, the interference model is set up to calculate the statistical charactcrisitics of interference. then the close formula for the probability of being no isolated node is obtained. the simulation validates the correctness of the f

7、ormula and shows that the interference in the dense network will increase, it is useful to improve the network connectivity by distributing the node rationally and effectively.finally, interference suppression using csma protocol is investigated. the network model is set up based on matern point pro

8、cess and the new node density is obtained according to the interference model in csma network, the closed formula of connectivity probability is derived. from the simulation results, it is helpful to control interference and improve network connectivity by using csma protocol in ad hoc network.key w

9、ords： ad hoc network, connectivity, interference, wireless channel, media access control目錄專用術語注釋表1第一章緒論2無線ad hoc網(wǎng)絡概述2無線ad hoc網(wǎng)絡的發(fā)展2無線ad hoc網(wǎng)絡的特點21.1.3無線ad hoc網(wǎng)絡的關鍵技術31.2無線ad hoc網(wǎng)絡連通性研究背景及意義51.3本文主要研究內(nèi)容及結(jié)構(gòu)安排6第二章ad hoc網(wǎng)絡連通性基礎72.1 ad hoc網(wǎng)絡連通性研究相關工作72.2隨機幾何基礎102.2.1泊松點過程102.2.2 標記點過程112.3圖論基礎122.4本章小結(jié)15

10、第三章ad hoc網(wǎng)絡二連通性分析 163一維ad hoc網(wǎng)絡二連通性分析 163.1.1模型建立及連通性分析163.1.2仿真結(jié)果與分析193.2二維 ad hoc網(wǎng)絡二連通性問題 213.2.1增強網(wǎng)絡連通性的單節(jié)點移動算法213.2.2仿真結(jié)果與分析273.3本章小結(jié)28第四章 衰落信道下基于干擾的ad hoc網(wǎng)絡連通性分析304無線信道介紹304.2衰落信道下ad hoc網(wǎng)絡連通性分析304.2.1連通概率分析314.2.2仿真結(jié)果與分析344.3干擾對ad hoc網(wǎng)絡連通性的彩響364.3.1干擾模型364.3.2連通概率分析384.3.3仿真結(jié)果與分析414.4本章小結(jié)44第五章基

11、于csma的無線ad hoc網(wǎng)絡連通性分析455.1路徑損耗模型下csma網(wǎng)絡連通性分析455.1.1模型建立以及連通性分析465.1.2仿真結(jié)果與分析485.2衰落信道下csma網(wǎng)絡連通性分析495.2.1模型建立以及連通性分析495.2.2仿真結(jié)果與分析535.3本章小結(jié)56第六章總結(jié)與展望57參考文獻59附錄1程序清單62附錄2攻讀碩士學位期間撰寫的論文64附錄3攻讀碩士學位期間參加的科研項目 65致謝66專用術語注釋表縮略詞說明：aodvapad-hoc on-demand distance vector routingaccess point自組織按需距離矢量路由 接入點無線基本接入

12、bapubasic access protocol solutions for wireless協(xié)議方案碼分多址 累積分布函數(shù)載波偵聽cdmacode division multiple access多路訪問美國防部高級cdfcumulative distribution function研究計劃局雙忙音多重接csmacarrier sense multiple access入darpadefense advanced research project agencydbtmadual busy tone multiple accessdfsdepth-first-search深度優(yōu)先搜索dsd

13、vdestination-sequenceddistance-vector目的序列距離矢量dsrdynamic source routing動態(tài)源路由協(xié)議glomoglobal mobile information systems金球移動信息系統(tǒng)hrmahop-reservation multiple access跳隙預留多重接入lprlow-cost packet radio低開銷報文無線技術macmedia access control媒體接入控制macamultiple access collision avoidance沖突避免多路訪問manetmobile ad hoc networ

14、k移動ad hoc網(wǎng)絡mimomultiple-input multiple-out-put多輸入多輸出mppmatem ponit processmatern點過程npnondeterministic polynomial非確定性多項式panpersonal area network個人局域網(wǎng)pdfprobability distribution function概率分布函數(shù)ppppoisson point process泊松點過程prnetpacket radio network分組無線電網(wǎng)絡qosquality of service服務質(zhì)量rwprandom waypoint隨機路點模型

15、sirsignal-to-interference ratio信干比sinrsignal-to-interference-noise ratio信干噪比snrsignal-to-noise ratio信噪比suransurvivable adaptive network可存活性自適應網(wǎng)絡tdmatime division multiple access時分多址wlanwireless local area network無線局域網(wǎng)第一章緒論無線ad hoc網(wǎng)絡概述無線ad hoc網(wǎng)絡又被稱為無線多跳網(wǎng)絡或自組織網(wǎng)絡，它是由一組地位平等且功能相對 完善的無線收發(fā)裝置組成的臨時自治系統(tǒng)。網(wǎng)絡中沒有

16、集中控制中心，各個節(jié)點通過無線鏈 路建立連接并相互協(xié)作，進而實現(xiàn)網(wǎng)絡的互連與共享。無線ad hoc網(wǎng)絡的發(fā)展最早開始進行ad hoc網(wǎng)絡的研究是始于上個世紀七十年代，當時稱為分組無線電網(wǎng)絡 (prnet)。1972年，首先是由美國國防部高級研究計劃局(darpa)針對在戰(zhàn)場中的應用， 開始了該項目的研究。為了實現(xiàn)更大規(guī)模的組網(wǎng)，1983年，darpa開始進行可存活性自適 應網(wǎng)絡(suran)項目的研究2】,使得prnet能夠支持低功耗電臺的接入。1987年，繼suran 后，darpa又研發(fā)岀低開銷報文無線技術(lpr)的自適應網(wǎng)絡協(xié)議，該協(xié)議使得prnet 能夠適應快速變化的戰(zhàn)場環(huán)境。199

17、4年，在之前的基礎上，darpa開啟了一個更為全面深 入的項目一全球移動信息系統(tǒng)(glomo)，旨在開發(fā)出能夠滿足軍事需耍、可快速組網(wǎng)的 移動信息系統(tǒng)。隨著軟硬件技術的快速發(fā)展，這樣的自組織網(wǎng)絡逐步成熟，受到了各國的高 度重視。為了讓這種網(wǎng)絡獲得更人的發(fā)展，1991年，ieee802.1標準委員會將這種自組織、 對等式、多跳的分布式無線網(wǎng)命名為“ad hoc網(wǎng)絡”，ad hoc網(wǎng)絡由此誕生。ad hoc網(wǎng)絡 最初的研究與布置是為了滿足軍事通信的應用，隨著無線網(wǎng)絡技術的不斷成熟，ad hoc網(wǎng)絡 也開始進入商業(yè)與民用領域，目前，己有國外運營商開始應用ad hoc網(wǎng)絡與固定基礎設施網(wǎng) 絡相結(jié)合的新

18、技術，如超寬帶無線技術(ultra wide-band radio technology)、藍牙技術 (bluetooth).家庭無線網(wǎng)(homerf)等無線通信新技術成為有線網(wǎng)絡與蜂窩系統(tǒng)網(wǎng)絡的發(fā)展 和補充。無線ad hoc網(wǎng)絡的特點ad hoc網(wǎng)絡作為一種特殊的組網(wǎng)方式，不依賴于固定網(wǎng)絡設施就可以在任何時間任何地 點獨立組網(wǎng)。網(wǎng)絡屮，每個節(jié)點的地位是平等的，不存在屮心控制節(jié)點，網(wǎng)絡中的節(jié)點不僅 能夠像普通終端一樣接收處理信息，還具備路由轉(zhuǎn)發(fā)功能，具有較強的靈活性?？傮w來說， ad hoc網(wǎng)絡具有以下的特點：(1) 分布式組網(wǎng)。ad hoc網(wǎng)絡中沒有中心控制節(jié)點，網(wǎng)絡中的各個節(jié)點地位是平等的

19、， 網(wǎng)絡的協(xié)同工作主要依靠其所建立的分布式算法，它沒有其他任何預設的基礎設施，通過自 發(fā)組織在無人工干預的情況下即可實現(xiàn)隨時隨地快速布網(wǎng)。(2) 網(wǎng)絡拓撲動態(tài)變化。ad hoc網(wǎng)絡屮的任意節(jié)點不受其他節(jié)點控制，能夠自由地開 關通信電臺、移動和調(diào)節(jié)發(fā)送功率，同時由于地理環(huán)境和無線信道等因素的影響，網(wǎng)絡的拓 撲結(jié)構(gòu)是動態(tài)變化的，并且變化的趨勢、方向、速度都是未知的。(3) 有限的傳輸帶寬。ad hoc網(wǎng)絡是利用無線信道進行通信，無線信道本身所能提供 的帶寬要比有線信道小的多。同吋，考慮到網(wǎng)絡中的干擾、噪聲和動態(tài)變化的拓撲等因素， 網(wǎng)絡屮的節(jié)點實際所獲得帶寬要遠遠小于理論帶寬。(4) 低安全性。ad

20、 hoc網(wǎng)絡的安全性也是一個薄弱環(huán)節(jié)，這是由于網(wǎng)絡中沒有中心控 制節(jié)點，并且采用無線信道通信以及分布式控制技術，使得網(wǎng)絡容易遭到攻擊、竊聽等威脅。 因此，網(wǎng)絡安全技術是ad hoc網(wǎng)絡重點研究方向，需要引入抗干擾、加密、認證與簽名等安 全技術。(5) 多跳路由。ad hoc網(wǎng)絡中單個節(jié)點的發(fā)射功率和能量有限，因此其通信范圍也是 有限的，為了能夠與全網(wǎng)內(nèi)其他任意節(jié)點建立連接，往往需要通過其他節(jié)點經(jīng)過多跳路由轉(zhuǎn) 發(fā)完成。ad hoc網(wǎng)絡屮的節(jié)點自身即具備路由轉(zhuǎn)發(fā)功能，而不需要利用專門的路由設備。(6) 能耗問題。ad hoc網(wǎng)絡主要應用于野外、戰(zhàn)場等場合，通常節(jié)點的能量只能依靠 蓄電池供給，能量儲

21、備有限，能量問題是ad hoc網(wǎng)絡的瓶頸在能量儲備有限的情況下， 需要研究節(jié)能技術來提高ad hoc網(wǎng)絡的生存周期。無線ad hoc網(wǎng)絡的尖鍵技術ad hoc網(wǎng)絡不同于傳統(tǒng)的固定基礎設施網(wǎng)絡，它的拓撲結(jié)構(gòu)是動態(tài)變化的，因此傳統(tǒng)網(wǎng) 絡中的一些技術無法被直接使用，需要另外的一些專用協(xié)議和技術保證網(wǎng)絡的協(xié)同工作。目 前，ad hoc網(wǎng)絡的熱點研究方向主要包括信道接入技術、路由協(xié)議、服務質(zhì)量、安全問題、 網(wǎng)絡能耗、連通性等。(1) 接入技術按照ad hoc網(wǎng)絡信道接入?yún)f(xié)議使用的信道數(shù)目可劃分為單信道，雙信道，多信道接入?yún)f(xié) 議。單信道的ad hoc網(wǎng)絡只有一個共享信道，所有的控制報文和數(shù)據(jù)報文都在同一個

22、信道傳 輸。由于隱蔽終端、暴露終端和傳播時延等因素的影響，單信道ad hoc網(wǎng)絡可能產(chǎn)生報文沖 突。一般來說，數(shù)據(jù)報文要比控制報文長的多，數(shù)據(jù)報文的沖突會嚴重影響信道利用率。因此，單信道接入?yún)f(xié)議的主要目標之一就是設計合適的沖突避免機制，利用控制報文盡量減少 其至消除數(shù)據(jù)報文沖突。典型的基于單信道的ad hoc網(wǎng)絡信道接入?yún)f(xié)議maca (multiple access collision avoidance)> csma (carrier sense multiple access)等。雙信道 ad hoc 網(wǎng)絡 有兩個共享信道，為控制信道和數(shù)據(jù)信道，控制信道只傳控制報文，數(shù)據(jù)信道只傳數(shù)據(jù)

23、報文， 如此就不會產(chǎn)生控制報文與數(shù)據(jù)報文的沖突，能夠有效解決隱蔽終端和暴露終端問題。典型 的雙信道接入?yún)f(xié)議有無線基木接入?yún)f(xié)議方案(basic access protocol solutions for wireless, bapu) 和雙忙咅多重接入(dual busy tone multiple access, dbtma)等。多信道ad hoc網(wǎng)絡的接入 機制更加靈活，這種信道接入?yún)f(xié)議主要關注兩個問題：信道分配和接入控制。信道分配負責 為不同的通信節(jié)點分配相應的信道，消除數(shù)據(jù)報文沖突，使盡量多的節(jié)點能夠同時通信。接 入控制負責調(diào)整節(jié)點接入信道的時機、沖突避免等。典型的多信道接入?yún)f(xié)議有：多信

24、道載波 偵聽接入(multiplechannelcsma)、跳隙預留多重接入(hop-reservation multiple access, hrma) 等。木文第五章的研究就是采用基于單信道的信道接入?yún)f(xié)議csmao(2) 路由協(xié)議ad hoc網(wǎng)絡與傳統(tǒng)網(wǎng)絡不同，路由節(jié)點的主要挑戰(zhàn)是所存儲的分布式路由數(shù)據(jù)庫如何適 應網(wǎng)絡拓撲的動態(tài)變化。因此，必須設計一個專用的，高效的無線多跳路由協(xié)議。目前，一 般廣泛認可的代表性成果有 dsr(dynamic source routing)> dsdv(destination-sequenced distance-vector routing)7 ao

25、dv (ad-hoc on-demand distance vector)岡等。dsr是一種 源路由驅(qū)動的按需路由協(xié)議，主要包括路徑搜索和路由維護，允許節(jié)點動態(tài)地發(fā)現(xiàn)多跳路由。 dsdv是一種基于bellman-ford路由算法的主動路由協(xié)議，被認為是最早的無線多跳網(wǎng)絡路 由協(xié)議，它采用序列號來區(qū)分路由的新舊程度，防止距離矢量路由協(xié)議中可能發(fā)生的無窮環(huán) 路問題。aodv也是一種按需路由協(xié)議，它結(jié)合了 dsr和dsdv,以dsdv為基礎，結(jié)合 dsr的按需路由算法并加以改進而成。到目前為止，ad hoc網(wǎng)絡的路由協(xié)議研究是最為豐富 和集中的。(3) 服務質(zhì)量早期ad hoc網(wǎng)絡只需要傳輸少量的信

26、息，隨著應用領域的不斷擴大，需要在ad hoc網(wǎng) 絡中開展多媒體業(yè)務，這需要很高的網(wǎng)絡延遲和抖動要求，即需要一定的qos保證。服務質(zhì) 量保證是ad hoc網(wǎng)絡的一個系統(tǒng)性問題，需要在每一層都建立相應機制。(4) 安全問題ad hoc網(wǎng)絡的安全性較差，容易受到竊聽、攔截和攻擊，因此，開發(fā)ad hoc網(wǎng)絡安全 技術并構(gòu)建ad hoc網(wǎng)絡的安全體系結(jié)構(gòu)是重點研究方向之一。(5) 網(wǎng)絡能耗問題ad hoc網(wǎng)絡通常應用在郊外、戰(zhàn)場等場合，節(jié)點能量儲備有限，能耗問題突出。目前主 要的硏究方向為節(jié)點采用自適應功率，通過調(diào)節(jié)功率盡量減少干擾并且達到最大的覆蓋范圍。 另外，還有智能休眠等機制的應用，來達到減少網(wǎng)

27、絡能耗的目的。（6）連通性連通性是無線ad hoc網(wǎng)絡向用戶提供可靠應用的先決條件,一個連通網(wǎng)絡必須保證任意 兩個節(jié)點之間至少存在一條鏈路，這條鏈路可以是一跳，也可以多跳。當存在某兩個節(jié)點之 間沒有鏈路時，該網(wǎng)絡不連通。連通性決定了節(jié)點間數(shù)據(jù)傳輸?shù)某晒β?，同吋保持網(wǎng)絡連通 是網(wǎng)絡路由層設計的一個基本保證?？傊?，任何的網(wǎng)絡設計都需要建立在網(wǎng)絡連通的基礎上。1.2無線ad hoc網(wǎng)絡連通性研究背景及意義連通性是網(wǎng)絡的一個基本屬性。有線網(wǎng)絡中，節(jié)點依靠有線信道例如明線、電纜、光纖 等來建立鏈路，一旦網(wǎng)絡的布線完成，只要線路沒有損壞，網(wǎng)絡的連通性就不會被改變，因 此，連通性問題一直被人們所忽視。隨著無

28、線網(wǎng)絡的廣泛應用，連通性問題慢慢引起人們的 重視。在基礎設施網(wǎng)絡中，連通性問題常常同網(wǎng)絡的覆蓋問題一起進行研究。因為在這種網(wǎng) 絡結(jié)構(gòu)中，只要移動終端在一個中心控制器（例如基站，ap等）的覆蓋范圍內(nèi)，終端就能接 入網(wǎng)絡進行正常通信。然而與基礎設施網(wǎng)絡屮的連通性問題相比，影響ad hoc網(wǎng)絡的連通性 因素更加復雜，該問題的研究更加具有挑戰(zhàn)性r更有意義。連通性是ad hoc網(wǎng)絡的先決條件。在ad hoc網(wǎng)絡這種自組織網(wǎng)絡中，節(jié)點間鏈路受到 網(wǎng)絡中其他節(jié)點的位置、節(jié)點發(fā)射功率、無線信道環(huán)境等因素的影響，且鏈路的存在有兩種 效應：一方面應盡可能多的建立鏈路，使得節(jié)點能夠找到僅需少數(shù)跳數(shù)的路由將信息傳送至

29、 目的節(jié)點，如此能夠減少節(jié)點的路由負擔；另一方面大量鏈路的建立會增大節(jié)點間干擾，從 而減小了網(wǎng)絡容量。因此，需要對鏈路的建立進行最優(yōu)化的考慮。早期的一些學者提出，如 果發(fā)射半徑為廠，則路由負擔按照0（1/廠）增長，干擾則是按照（xt）增長，兩者的等效比值是 根據(jù)。（廠）增長，也就是說發(fā)射半徑廠越小越好刃。但是廠過小會導致網(wǎng)絡不連通，因此需要調(diào) 節(jié)網(wǎng)絡節(jié)點密度（定義為單位面積內(nèi)平均節(jié)點個數(shù)）或者節(jié)點發(fā)射半徑（由發(fā)射功率決定） 來保持網(wǎng)絡的連通。另外，無線信道的惡劣環(huán)境以及節(jié)點移動等因素都會給無線ad hoc網(wǎng)絡 連通性研究增加難度。連通性對無線ad hoc網(wǎng)絡的設計具有非常重要的意義。它是路由算

30、法實現(xiàn)的基礎，網(wǎng)絡 只有在全連通的基礎上才能夠找到任意兩節(jié)點間的路由使得信息經(jīng)過多跳路由成功發(fā)送。此 外，連通性問題的研究對無線ad hoc網(wǎng)絡的網(wǎng)絡架構(gòu)、拓撲優(yōu)化、節(jié)點功率控制以及網(wǎng)絡層仿真也都具有非常重要的意義。1.3本文主要研究內(nèi)容及結(jié)構(gòu)安排本論文的研究獲得了國家白然科學基金“基于隨機幾何的多跳無線網(wǎng)絡干擾模型及跨層 容量優(yōu)化技術研究”的支持。本文的組織架構(gòu)如下：第一章首先概述了無線ad hoc網(wǎng)絡的發(fā)展歷程，網(wǎng)絡特點，應用和關鍵技術，并敘述了 連通性問題的研究背景以及意義。第二章論述了近年來國內(nèi)外對于無線ad hoc網(wǎng)絡連通性問題研究的相關工作，對本文研 究ad hoc網(wǎng)路連通性問題所

31、涉及的隨機幾何、圖論等基礎知識進行介紹。第三章主要研究如何構(gòu)造具有二連通的網(wǎng)絡拓撲結(jié)構(gòu)以增強ad hoc網(wǎng)絡連通性。首先從 概率的角度研究一維ad hoc網(wǎng)絡實現(xiàn)2連通的基本條件，其次針對二維ad hoc網(wǎng)絡，研究 一種基于接收信號強度的節(jié)點移動算法，保證網(wǎng)絡的二連通性，達到優(yōu)化網(wǎng)絡拓撲的目的， 并進行相應的仿真分析。第四章首先研究了衰落信道下二維ad hoc網(wǎng)絡的連通性問題，推導了網(wǎng)絡連通概率。隨 后重點考慮干擾對ad hoc網(wǎng)絡的影響，給出干擾模型，推導了網(wǎng)絡連通概率閉合式，并通過 仿真結(jié)果驗證理論分析的止確性。第五章考慮mac層相關協(xié)議，信道接入使用csma協(xié)議來抑制干擾，在不同的信道模

32、 型下研究ad hoc網(wǎng)絡連通性問題，推導了網(wǎng)絡連通概率的閉合式。第六章對本文工作內(nèi)容進行總結(jié)，并且給岀未來無線ad hoc網(wǎng)絡連通性問題的進一步研 究方向。第二章ad hoc網(wǎng)絡連通性基礎對于無線ad hoc網(wǎng)絡連通性的研究最早可以追溯到上世紀七十年代，當時gilbert研究 了無線廣播站的多跳連通性問題，他證明了系統(tǒng)存在一個域值節(jié)點密度，當網(wǎng)絡密度大于它 時，長距離多跳通信是有可能的，同時也奠定了連續(xù)流滲理論的基礎。隨著ad hoc網(wǎng)絡 的應用由軍事領域開始進入民用商用領域，ad hoc網(wǎng)絡的研究越來越廣泛，而連通性問題的 研究正越來越受到重視，所研究的方面也越來越廣泛。目前，ad hoc

33、網(wǎng)絡連通性分析所采用 的理論基礎包括滲流理論、隨機兒何理論和圖論等，對靜態(tài)ad hoc網(wǎng)絡、移動ad hoc網(wǎng)絡， 確定性和隨機性無線信道下的ad hoc網(wǎng)絡等多種情況下的的連通性問題都進行了全面而深 入的研究。2.1 ad hoc網(wǎng)絡連通性研究相關工作（1）確定性信道以及隨機性信道下的ad hoc網(wǎng)絡連通性研究ad hoc網(wǎng)絡連通性問題主要研究網(wǎng)絡連通概率、節(jié)點密度、域值發(fā)射范圍（網(wǎng)絡達到連 通所需最小發(fā)射半徑）、鄰節(jié)點個數(shù)等網(wǎng)絡基本參數(shù)之間的定性與定量關系。人多研究基于確 定性模型，例如圓盤模型。基于該模型，文獻11針對一維靜態(tài)ad hoc網(wǎng)絡進行了研究，推 導了網(wǎng)絡漸進連通閉合公式，得到

34、了網(wǎng)絡連通概率與節(jié)點密度、發(fā)射半徑等網(wǎng)絡參數(shù)z間的 定量關系。針對二維ad hoc網(wǎng)絡，文獻12研究了在二維無限平面上保持網(wǎng)絡漸進連通所需 的最小發(fā)射功率。在此基礎上，許多學者開始研究如何增強ad hoc網(wǎng)絡的容錯能力，也就是 網(wǎng)絡達到k連通所需要的條件。文獻13在二維泊松ad hoc網(wǎng)絡中對保持網(wǎng)絡連通以及k- 連通所需耍的最小節(jié)點度問題進行了研究；文獻14給出了保持網(wǎng)絡k連通所需的臨界發(fā)射 半徑以及每個節(jié)點所需的鄰節(jié)點數(shù)；文獻15針對有界的無線ad hoc網(wǎng)絡，以定理的形式給 出了網(wǎng)絡達到k連通的所需條件，并給岀了相關證明。確定性模型僅考慮無線信號的路徑損 耗，由于實際信道環(huán)境的復雜多變，

35、還需要考慮無線信道的衰落特性。文獻16最早引入了 信道隨機性，在確定性信道模型上疊加對數(shù)陰影衰落，在對數(shù)陰影衰落信道下研究ad hoc 網(wǎng)絡連通性問題，最終得出了網(wǎng)絡連通所需要的最小節(jié)點度。文獻17推導了 adhoc網(wǎng)絡中 任意兩節(jié)點存在鏈路的概率，給出了保持網(wǎng)絡連通所需的最小節(jié)點度以及最大連通分量。文 獻18詳細討論了信道隨機性對ad hoc網(wǎng)絡連通性的影響，給出了對數(shù)陰影衰落，瑞利衰落 信道下網(wǎng)絡連通概率表達式。文獻19以定理形式給出了瑞利衰落信道下網(wǎng)絡中任意節(jié)點成 為孤立節(jié)點的概率，并給出相關證明，并推導了網(wǎng)絡連通概率。(2) 基于滲流理論的ad hoc網(wǎng)絡連通性研究 隨機圖理論的研究屮

36、得到一個的重要發(fā)現(xiàn)：存在出現(xiàn)全連通的臨界概率。也就是說，網(wǎng)絡具有臨界連通概率"，當不超過時，網(wǎng)絡由孤立節(jié)點集群組成；當超過°時則節(jié)點集群 擴展至整個網(wǎng)絡。這一發(fā)現(xiàn)與滲流理論極為相似，因此，滲流理論逐漸開始應用于ad hoc 網(wǎng)絡的連通性研究中。流滲理論包括點滲流和邊滲流，重點研究整個圖到達流滲狀態(tài)時點或 者邊所需的打開概率。文獻20利用流滲理論分析了干擾對ad hoc網(wǎng)絡連通性的影響，給岀 了網(wǎng)絡達到漸進連通時節(jié)點密度的臨界值。文獻21也是基于滲流理論，從網(wǎng)絡連通分量的 角度研究了網(wǎng)絡連通性問題，分析其中的節(jié)點個數(shù)占網(wǎng)絡總節(jié)點個數(shù)的百分比，并通過計算 機仿真驗證了分析結(jié)果的

37、止確性。(3) 移動ad hoc網(wǎng)絡連通性研究manet網(wǎng)絡(移動ad hoc網(wǎng)絡)的連通性問題也受到了廣泛的關注。多數(shù)情況下研究 一維高速移動ad hoc網(wǎng)絡，該網(wǎng)絡具有非常實際的應用意義，即高速車載網(wǎng)絡。大部分的研 究基于隨機路點(rwp)模型，該模型屮節(jié)點可以向任意方向以任意速度進行移動，文獻22 對rwp模型下的節(jié)點分布模型進行了分析，最終給出了在節(jié)點的停止時間為獨立均勻條件下 的節(jié)點分布模型。文獻23對rwp模型進行了詳細分析，討論了網(wǎng)絡基木參數(shù)之間的關系， 參數(shù)z間的關系，最后通過仿真說明該模型的優(yōu)缺點以及適用場景。文獻24在節(jié)點任意分 布的一維ad hoc網(wǎng)絡下，分別討論了i古i

38、定節(jié)點密度以及隨時間變化的節(jié)點密度兩種情況下的 網(wǎng)絡連通概率。針對二維移動ad hoc網(wǎng)絡，文獻25在研究連通性的基礎上考慮網(wǎng)絡能耗， 對比幾種不同的網(wǎng)絡拓撲結(jié)構(gòu)，在保證網(wǎng)絡連通的基礎上所需的網(wǎng)絡能耗。此外，還有許多 研究基于其他節(jié)點移動模型，文獻26在陰影衰落信道下分析了不同移動ad hoc模型的連通 性問題，給出了定性的分析表達式。文獻27,28基于m-like節(jié)點移動模型分析了網(wǎng)絡連通 概率，給出了在該模型下網(wǎng)絡的臨界通信半徑為c ln/(n/z)o(4) 網(wǎng)絡覆蓋與連通性問題與連通性緊密相關的還包括網(wǎng)絡的覆蓋問題，如皿匚些研究認為覆蓋問題即為連通性 問題，許多學者證實了兩者并不等效，對

39、于ad hoc網(wǎng)絡的組網(wǎng)，應當在保持網(wǎng)絡連通的同時 盡可能增大覆蓋范圍。文獻29研究了一維ad hoc網(wǎng)絡覆蓋和連通性問題，分別給出了網(wǎng)絡 規(guī)模無線人時達到全覆蓋和全連通所需的節(jié)點發(fā)射半徑，并口證明了網(wǎng)絡達到全連通所需的 臨界發(fā)射半徑要大于網(wǎng)絡全覆蓋所需的臨界發(fā)射半徑。文獻30研究了二維ad hoc網(wǎng)絡的覆 蓋和連通性問題，提出了一種節(jié)點覆蓋算法，在保證網(wǎng)絡連通的同時盡量增大覆蓋范圍。(5) 基于干擾的ad hoc網(wǎng)絡連通性研究由于無線網(wǎng)絡中節(jié)點間干擾的不可避免，基于干擾的連通性分析也是ad hoc網(wǎng)絡研究的熱點。31綜述了無線ad hoc網(wǎng)絡干擾建模的方法，討論了各種情況下的干擾模型，利用隨

40、 機幾何或者干擾圖來描述干擾統(tǒng)計規(guī)律，不同的場景應選擇對應的干擾模型。32提出了一 種一維ad hoc網(wǎng)絡的干擾模型，該模型適用于高速車載網(wǎng)絡。33針對二維ad hoc網(wǎng)絡， 在瑞利衰落信道下，采用a 穩(wěn)態(tài)分布描述干擾統(tǒng)計規(guī)律，得到了兩節(jié)點成功通信的概率。在 此基礎上，34進一步研究得岀了兩節(jié)點成功通信的概率表達式可以由干擾的特征函數(shù)表示。 35在泊松ad hoc網(wǎng)絡下，利用散粒噪聲理論建立干擾模型，推導了瑞利衰落信道下基于sir 的中斷概率公式。36以圖論為基礎，研究了在nakagami-m衰落信道下，考慮節(jié)點間相互干 擾，推導出了網(wǎng)絡連通概率的閉合公式。(6) 基于mac層協(xié)議的ad ho

41、c網(wǎng)絡連通性研究對ad hoc網(wǎng)絡連通性具有重要影響的因素還包括信道接入機制。ad hoc網(wǎng)絡中常用的 mac層協(xié)議有aloha協(xié)議和csma協(xié)議。aloha協(xié)議下每個節(jié)點擁有概率為p的發(fā)送概 率，降低了同時發(fā)送的網(wǎng)絡節(jié)點數(shù)口，從而達到控制干擾的fi的。csma協(xié)議在節(jié)點發(fā)送分 組之前監(jiān)測信道使用情況，檢測其它用戶是否正在使用信道，一旦信道空閑就立即發(fā)送分組， 這是一種更加高效的mac層協(xié)議，其信道利用率大大高于aloha協(xié)議。37基于aloha 和csma協(xié)議，分別推導了有限ad hoc網(wǎng)絡中斷概率的閉合表達式，并對比了兩種協(xié)議下 的網(wǎng)絡性能。38基于非時隙aloha,推導了 manet網(wǎng)絡

42、中sir統(tǒng)計規(guī)律，并同吋隙aloha 網(wǎng)絡進行了比較。同樣在manet網(wǎng)絡中，39對mac層協(xié)議下的網(wǎng)絡性能進行了對比，并 給出了網(wǎng)絡容量的閉合表達式。40在泊松網(wǎng)絡下基于時隙aloha協(xié)議分析了干擾的統(tǒng)計 規(guī)律，得到了干擾的特征函數(shù)，進而推導網(wǎng)絡中斷概率以及容量。41基于隨機幾何mpp (matem ponit process)理論建立csma網(wǎng)絡模型，推導了該網(wǎng)絡模型下的節(jié)點密度以及平 均干擾功率。(7) 其他方面的一些研究 連通性的研究還包括許多方面。基于圖論的連通性研究也是常見 情況，42將網(wǎng)絡連通性與圖論相關聯(lián)，得出了網(wǎng)絡連通性與最小生成樹的關系。43證明了網(wǎng)絡連通問題是np完 全問

43、題，提出了一種關鍵節(jié)點算法，給出了如何在網(wǎng)絡中加入關鍵節(jié)點使得網(wǎng)絡連通的方法。 固定拓撲結(jié)構(gòu)下的連通性問題也受到關注，44在固定拓撲的場景下，分析了陰影衰落、瑞 利衰落、nakagamim衰落信道對網(wǎng)絡連通性的影響，并給出了網(wǎng)絡連通概率表達式。45研 究了在特定拓撲下如何改善網(wǎng)絡連通性，通過信號強度感知移動某些節(jié)點消除網(wǎng)絡割點從而增強網(wǎng)絡連通性。此外，為了進一步提升網(wǎng)絡連通性能，mimo技術也開始引入至ad hoc 網(wǎng)絡，46在采用定向發(fā)送天線的ad hoc網(wǎng)絡場景下，分析了網(wǎng)絡漸進連通概率，給出了網(wǎng) 絡漸進連通時所需的臨界發(fā)射功率。47在ad hoc網(wǎng)絡mimo信道下，基于sinr推導了網(wǎng)

44、絡連通概率，并通過仿真驗證了衰落信道環(huán)境屮采用多天線技術有利于克服信號衰減，增強 網(wǎng)絡的連通性。48研究了 mimo ad hoc網(wǎng)絡中干擾問題，并給出了該場景下網(wǎng)絡連通性能, 通過網(wǎng)絡連通性能的比較分析干擾對ad hoc網(wǎng)絡的影響。本文主要基于圖論、點過程理論和概率統(tǒng)計等相關數(shù)學知識進行ad hoc網(wǎng)絡連通性分 析，下而對所運用的相關知識進行簡單闡述。2.2隨機幾何基礎運用隨機幾何理論研究無線網(wǎng)絡模型最早起源于1961年,gilbert首次利用連續(xù)布爾滲流 模型、泊松模型等理論對大規(guī)模無線網(wǎng)絡的連通性問題進行了研究刃。然而之后的二十多年 中很少有人進行相關研究，直至2000年左右，利用隨機兒

45、何中的一些性質(zhì)分析大規(guī)模無線多 跳網(wǎng)絡的研究開始大量出現(xiàn)。隨機幾何是建立在幾何學、概率論和測度論基礎上的，它是研 究歐式空間內(nèi)隨機節(jié)點分布的數(shù)學理論。ad hoc網(wǎng)絡中任意節(jié)點的地位是平等的，可以看作 某空間區(qū)域上的點集，因此，可以利用隨機兒何理論，建立空間兒何模型來描述ad hoc網(wǎng)絡 節(jié)點的分布規(guī)律。泊松點過程經(jīng)典隨機兒何理論中最基本的是點過程理論，尤其是泊松點過程?？紤]d維的歐氏空間 為疋，可以定義一個空間點過程 為剋上有限或者是無限可數(shù)的點集。通常，將點過程 表示為空間疋上的一個離散測度，表達為：(2.1)其中j表示在兀的狄拉克測度，對于au “，若xu a,則e /a) = 1；若兀

46、年a,則e ") = 0,r 因此c1(a)表示集合a中點的數(shù)目。此外，對于所有定義在肥上的實函數(shù)有等式設a為肥上的有限非空測度，則密度測度為a的泊松點過程可以定義為有限維分布:p(a)二斤,(a)二兄i 1k k(2.2)k (a extn罟/=!竹其中k - 1,2,., a，i = l，2,.m有界且互不相關。若密度測度不變a (dx) - x dx,則稱這樣的泊 松點過程為齊次泊松點過程，入表示網(wǎng)絡節(jié)點密度。點過程的稀釋性質(zhì)：考慮密度測度為a的泊松點過程以及函數(shù)”，函數(shù)"為疋至0,1 上的映射，則經(jīng)過函數(shù)卩稀釋后為：(2.3)£訛其中為獨立隨機變量，且滿足

47、p5= 1|o= 1- 8 = 0|®= p(x ),“為稀釋后的點過程，它仍然為泊松點過程，且密度測度為0人,并滿足(°a)(a)二f p(x) a (dx) , a為肥 a上的非空子集。這種稀釋點過程的一個典型的應用就是采用aloha協(xié)議的泊松點過程adhoc網(wǎng)絡，每個節(jié)點以概率°獲得令牌壞發(fā)送信號，此時，整個網(wǎng)絡可以看成是對原網(wǎng)絡的稀 釋，網(wǎng)絡節(jié)點密度為入。泊松點過程另一個非常重要的性質(zhì)是：對于齊次泊松點過程，增加或 者減少某個點2后不影響之前的點過程分布p! () = p()，p")表示去掉節(jié)點兀后的分布，這也是就著名 的axslivnyak 理

48、論。標記點過程標記點過程也是隨機兒何中常見的點過程之一，它的特別之處在于賦予了空間中每個節(jié)點一個附加屈性。它可以定義成是一種信息對的集合二(""),其中二匕是點的集合,"是屈性的集合，或者可以定義附帶屬性的點的集合為：(2.4)其中£(“)為狄拉克測度，"表示點兀的某種屬性，ad hoc網(wǎng)絡中，變量用可以表示節(jié)點的 發(fā)送概率，保護半徑等節(jié)點參數(shù)。mhc (matem hard core)點過程是一種標記點過程，它是在泊松點過程中，使得每個節(jié) 點具有半徑為力的排斥核空間，即構(gòu)成了 mhc點過程，其定義為：南京郵電大學碩士研究生學位論文第二章ad

49、hoc網(wǎng)絡連通性基礎(2.5)加c是點過程的一個稀釋，根據(jù)獨立泊松點過程的稀釋性質(zhì)可以，加c不是泊松 點過程，它的密度測度并不是簡單的入的線性函數(shù)。對于，bc/?00<6/<1,由slivnyak理論可知:c(fix(o,xl) = er j-' 1< uyj e bx(h) n o %) 0(t/(x?w)-baa胡林jp(dx)(bx(h) = 0dudx“de'xlth du-x av dhd一 (2.6)其中vd j/ r(l +j/2)為上球b的體積，令b=l,可以得至| - x vc = c(bx(0jxl) = _(2.7)mhc點過程的一個典型

50、的應用就是采用csma協(xié)議的泊松點過程ad hoc網(wǎng)絡，每個節(jié) 點具有一個載波偵聽半徑力，則對于節(jié)點密度為入的網(wǎng)絡，在任意時刻的激活節(jié)點密度即為,本文第五章的研究中ad hoc網(wǎng)絡mac層采用csma協(xié)議,itmhc mhc其節(jié)點服從mhc點過程。2.3圖論基礎對于網(wǎng)絡的研究離不開圖論，它不僅提供了描述網(wǎng)絡的語言，而且其結(jié)論被廣泛應用于 各種網(wǎng)絡的研究z中，下面簡單介紹圖論的基本概念和性質(zhì)。圖的二元組定義為g(v?e),其 中v是非空的頂點集合，e是v上二元關系即邊的集合，若v(g)和e(g)都是有限集合， 則稱圖g為有限圖，否則稱為無限圖。圖可以分為無向圖，有向圖。無向圖即為邊集e(g)中為

51、 無向邊，如圖2.1所示；有向圖即為邊集e(g)中為有向邊，如圖2.2所示；本文采用無向圖建立網(wǎng)絡模型，即認為任意收發(fā)節(jié)點間的無線信道是對稱的。12京郵電大學碩士研究生學位論文圖2.1無向圖圖2.3含孤立節(jié)點的圖圖2.4全連通圖結(jié)合本文的研究，下面介紹所涉及的圖論中一些基本概念：(1)邊:對于圖g(v,e),二元關系e(g)中的元素稱為邊。在ad hoc網(wǎng)絡中，邊是一 個基本研究對象，它表示任意兩節(jié)點之間的鏈路，在確定性信道中，鏈路是確定的；在衰落 型信道中，鏈路具有隨機性，是不確定的，以鏈路函數(shù)的形式呈現(xiàn)。(2 )路徑：對于圖g(v,e),以及圖中頂點u和八 如果存在頂點序列u = x,x2

52、,x3, 9xk = v,且(x,x/+1)e £(g),z = 1,2, ,k- ,則稱頂點序列?！浚?，鬲,，無為u到u 的一條路徑，路徑上邊的數(shù)fl稱為該路徑的長度，ad hoc網(wǎng)絡屮的任意兩節(jié)點間的跳數(shù)即等 于該路徑的長度。(3) 度：設uev(g),與頂點u和關聯(lián)的邊的數(shù)目稱為頂點u的度，記做d(u)。例如， 圖2.1中，“(vi) = 3。圖g中所有頂點的度數(shù)之和等于邊數(shù)的兩倍。(4) 鄰節(jié)點：設u e v(g),若某節(jié)點與頂點u有邊，則該節(jié)點即為節(jié)點u的鄰節(jié)點。(5) 孤立節(jié)點：對于圖g(v,e),圖中節(jié)點度為零的頂點稱為孤立節(jié)點，例如圖2.3中 的頂點v2即為圖中孤立

53、節(jié)點。若圖中存在孤立節(jié)點，則該圖一定不連通，但是若圖中不存在 孤立節(jié)點，則該圖不一定連通，也就是說，不存在孤立節(jié)點是圖連通的必要而非充分條件。(6) 連通圖：圖g(v,e)中，任意兩個頂點之間都能找到一條連通路徑，則稱圖g是連南京郵電大學碩士研究生學位論文通圖，否則稱為不連通圖，如圖2.1即為連通圖。第二章ad hoc網(wǎng)絡連通性基礎(7) 全連通圖：圖g(v,e)中，若任意兩頂點之間都存在邊，則稱g為全連通圖，如圖 2.4所示即為全連通圖。斤階全連通圖有c2 = ln(n - 1)條邊，全連通圖的連通性能最佳，對于“ 2全連通的網(wǎng)絡，任意節(jié)點失效均不會影響整個網(wǎng)絡的連通。(8) 割點：圖g(v

54、,e)為連通圖，去掉一個頂點以及該頂點所關聯(lián)的所有邊后，圖g不 再連通，則該頂點稱為圖g的割點。例如圖2.1,刪除頂點vi之后，原本連通的圖分割為v2、 v3?v4兩部分，因此vi是割點，而刪除v2,v3,v4任意一個頂點之后圖均保持連通，因此v2,v3,v4不是割點。割點對網(wǎng)絡來說非常重要，它是影響網(wǎng)絡健壯性的關鍵節(jié)點，一旦割點 失效，網(wǎng)絡就會不連通，因此，一個健壯的網(wǎng)絡拓撲需要考慮如何避免產(chǎn)生割點。關于割點 與二連通的關系可表述為：對于一個至少包含三個頂點的圖g(u,e), g二連通的充要條件為 g連通且圖屮不包含割點。本文第三章將對具有容錯能力的二連通ad hoc網(wǎng)絡進行研究。(9) 圖

55、的存儲方法。圖的存儲方法分為靜態(tài)存儲和動態(tài)存儲，靜態(tài)存儲主要有鄰接矩陣, 動態(tài)存儲主要包括鄰接表。木論文的仿真研究中將ad hoc網(wǎng)絡看成圖，采用鄰接矩陣表示網(wǎng) 絡結(jié)構(gòu)。a.鄰接矩陣：用以表示圖中各頂點間相鄰關系的矩陣。設圖g(v,e)具有個頂點，則g的鄰接矩陣為具有如下定義的斤階方陣：ai,7 = /%)或w'xjwe®。例如圖2.1的0反之鄰接矩陣為i1l1b.鄰接表:0 0 00 0 10 1 0鏈表中每個節(jié)用以表示每個頂點與其他節(jié)點所建立的鄰接關系的單鏈表,點包括兩部分：鄰接點域和鏈域。圖2的鄰接表表示方法如下:鄰接矩陣是一種順序存儲法，而鄰接表則是圖的一種鏈式存儲法

56、，不同的存儲方法可適用于不同的應用。對于一個斤階幺條邊的圖，采用這兩種存儲方法的優(yōu)劣勢如下表所示：表2.1圖的兩種存儲方法比較鄰接矩陣鄰接表優(yōu)點直觀方便，查找運算的時間復雜度為0(1)便于查找任意頂點的關聯(lián)邊及鄰節(jié)點，查找運算的吋間復雜度為o(e/n)缺點存儲稀疏圖，會造成很大的空間浪費不方便查找一個頂點的前驅(qū)頂點、以此頂點為終點的邊和該頂點的入度，需要掃描整個表，時間復雜度為o(e/n)適用場合處理1個頂點的度和關聯(lián)邊對任意頂點的關聯(lián)邊進行不斷重復運算空間復雜度o(n2)o(6e + 2/?)2.4本章小結(jié)對于ad hoc網(wǎng)絡連通性問題的研究，早期主要基于確定性信道，隨后引入了信道隨機性, 無線信道考慮小尺度衰落效應，研究網(wǎng)絡的連通性與節(jié)點密度、發(fā)射半徑等網(wǎng)絡基本參數(shù)z 間的關系。由于在臨界概率方面研究的相似性，滲流理論也被應用于連通性的研究z中，此 外，移動ad hoc網(wǎng)絡的研究也取得了大量成果，干擾模型，信道接入機制，mimo等技術 創(chuàng)新也不斷應用于ad hoc網(wǎng)絡之中，改善了網(wǎng)絡的連通性能。最后對本文所涉及的數(shù)學理論 知識進行簡單的介紹，包括隨機幾何點過程理論、圖論的基本概念及其性質(zhì)，為后序的研究 作一個基礎鋪墊。