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

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目錄專用術(shù)語注釋表1第一章緒論2無線ad hoc網(wǎng)絡(luò)概述2無線ad hoc網(wǎng)絡(luò)的發(fā)展2無線ad hoc網(wǎng)絡(luò)的特點(diǎn)21.1.3無線ad hoc網(wǎng)絡(luò)的關(guān)鍵技術(shù)31.2無線ad hoc網(wǎng)絡(luò)連通性研究背景及意義51.3本文主要研究內(nèi)容及結(jié)構(gòu)安排6第二章ad hoc網(wǎng)絡(luò)連通性基礎(chǔ)72.1 ad hoc網(wǎng)絡(luò)連通性研究相關(guān)工作72.2隨機(jī)幾何基礎(chǔ)102.2.1泊松點(diǎn)過程102.2.2 標(biāo)記點(diǎn)過程112.3圖論基礎(chǔ)122.4本章小結(jié)15

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

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

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跳隙預(yù)留多重接入lprlow-cost packet radio低開銷報文無線技術(shù)macmedia access control媒體接入控制macamultiple access collision avoidance沖突避免多路訪問manetmobile ad hoc networ

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

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

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

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

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

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

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

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

22、信道傳 輸。由于隱蔽終端、暴露終端和傳播時延等因素的影響，單信道ad hoc網(wǎng)絡(luò)可能產(chǎn)生報文沖 突。一般來說，數(shù)據(jù)報文要比控制報文長的多，數(shù)據(jù)報文的沖突會嚴(yán)重影響信道利用率。因此，單信道接入?yún)f(xié)議的主要目標(biāo)之一就是設(shè)計合適的沖突避免機(jī)制，利用控制報文盡量減少 其至消除數(shù)據(jù)報文沖突。典型的基于單信道的ad hoc網(wǎng)絡(luò)信道接入?yún)f(xié)議maca (multiple access collision avoidance)> csma (carrier sense multiple access)等。雙信道 ad hoc 網(wǎng)絡(luò) 有兩個共享信道，為控制信道和數(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)絡(luò)的接入 機(jī)制更加靈活，這種信道接入?yún)f(xié)議主要關(guān)注兩個問題：信道分配和接入控制。信道分配負(fù)責(zé) 為不同的通信節(jié)點(diǎn)分配相應(yīng)的信道，消除數(shù)據(jù)報文沖突，使盡量多的節(jié)點(diǎn)能夠同時通信。接 入控制負(fù)責(zé)調(diào)整節(jié)點(diǎn)接入信道的時機(jī)、沖突避免等。典型的多信道接入?yún)f(xié)議有：多信

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、題，提出了一種關(guān)鍵節(jié)點(diǎn)算法，給出了如何在網(wǎng)絡(luò)中加入關(guān)鍵節(jié)點(diǎn)使得網(wǎng)絡(luò)連通的方法。 固定拓?fù)浣Y(jié)構(gòu)下的連通性問題也受到關(guān)注，44在固定拓?fù)涞膱鼍跋拢治隽岁幱八ヂ?、?利衰落、nakagamim衰落信道對網(wǎng)絡(luò)連通性的影響，并給出了網(wǎng)絡(luò)連通概率表達(dá)式。45研 究了在特定拓?fù)湎氯绾胃纳凭W(wǎng)絡(luò)連通性，通過信號強(qiáng)度感知移動某些節(jié)點(diǎn)消除網(wǎng)絡(luò)割點(diǎn)從而增強(qiáng)網(wǎng)絡(luò)連通性。此外，為了進(jìn)一步提升網(wǎng)絡(luò)連通性能，mimo技術(shù)也開始引入至ad hoc 網(wǎng)絡(luò)，46在采用定向發(fā)送天線的ad hoc網(wǎng)絡(luò)場景下，分析了網(wǎng)絡(luò)漸進(jìn)連通概率，給出了網(wǎng) 絡(luò)漸進(jìn)連通時所需的臨界發(fā)射功率。47在ad hoc網(wǎng)絡(luò)mimo信道下，基于sinr推導(dǎo)了網(wǎng)

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

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

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

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

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

49、hoc網(wǎng)絡(luò)連通性基礎(chǔ)(2.5)加c是點(diǎn)過程的一個稀釋，根據(jù)獨(dú)立泊松點(diǎn)過程的稀釋性質(zhì)可以，加c不是泊松 點(diǎn)過程，它的密度測度并不是簡單的入的線性函數(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點(diǎn)過程的一個典型

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

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

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

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

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

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

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