無(wú)線網(wǎng)絡(luò)中保證覆蓋連通的節(jié)點(diǎn)部署問(wèn)題研究.pdf

1、無(wú)線網(wǎng)絡(luò)是當(dāng)前信息領(lǐng)域中的新研究熱點(diǎn)，具有廣泛的應(yīng)用前景。在較受關(guān)注的無(wú)線網(wǎng)絡(luò)中，無(wú)線傳感器網(wǎng)絡(luò)作為21世紀(jì)最具影響力的技術(shù)之一，由大量傳感器節(jié)點(diǎn)組成，通過(guò)節(jié)點(diǎn)收集、處理和傳輸來(lái)自物理世界的數(shù)據(jù)，為促進(jìn)人類生產(chǎn)、改善生活質(zhì)量提供服務(wù)。在無(wú)線移動(dòng)互聯(lián)網(wǎng)中，WiMAX作為寬帶無(wú)線接入的新興技術(shù)，使用大量中繼節(jié)點(diǎn)來(lái)覆蓋用戶并中轉(zhuǎn)信號(hào)，為用戶提供隨時(shí)隨地高速接入互聯(lián)網(wǎng)的服務(wù)，具有加強(qiáng)信號(hào)功率、減少信號(hào)衰減的作用，改善了用戶所收到的信號(hào)質(zhì)量。節(jié)點(diǎn)

2、作為這些無(wú)線網(wǎng)絡(luò)的基本組成部分，其部署方式?jīng)Q定了網(wǎng)絡(luò)的服務(wù)質(zhì)量。本文旨在設(shè)計(jì)優(yōu)化的節(jié)點(diǎn)部署方案，提高網(wǎng)絡(luò)服務(wù)質(zhì)量、降低網(wǎng)絡(luò)構(gòu)建成本。主要研究工作包括:
　　(1)在無(wú)線傳感器網(wǎng)絡(luò)中，任務(wù)區(qū)域邊界的存在導(dǎo)致“邊界效應(yīng)”，影響網(wǎng)絡(luò)的覆蓋和連通性能。針對(duì)此問(wèn)題，本文首先分析研究邊界附近節(jié)點(diǎn)的位置關(guān)系，然后基于此位置關(guān)系提出無(wú)邊界效應(yīng)部署算法GRLD，使用較少節(jié)點(diǎn)實(shí)現(xiàn)對(duì)任務(wù)區(qū)域的完全覆蓋和網(wǎng)絡(luò)連通。理論分析和仿真結(jié)果表明，算法GRLD部署

3、的網(wǎng)絡(luò)能覆蓋任意形狀區(qū)域，滿足常用連通覆蓋半徑比值(rc/rs≥0.54)下的網(wǎng)絡(luò)連通性。相對(duì)于已有的典型確定性部署算法，GRLD能保證對(duì)區(qū)域的無(wú)邊界覆蓋和網(wǎng)絡(luò)連通，具有較好的部署效率。
　　(2)在能量受限的傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)能耗約為感知和傳輸數(shù)據(jù)能耗的10至100倍。節(jié)點(diǎn)的移動(dòng)將導(dǎo)致節(jié)點(diǎn)能耗過(guò)大，導(dǎo)致其過(guò)快“死亡”，縮短網(wǎng)絡(luò)生命周期。針對(duì)此問(wèn)題，本文設(shè)計(jì)移動(dòng)節(jié)點(diǎn)部署算法，在保證目標(biāo)覆蓋和網(wǎng)絡(luò)連通的同時(shí)，降低節(jié)點(diǎn)的移動(dòng)能耗

4、。通過(guò)定義最小移動(dòng)代價(jià)的節(jié)點(diǎn)部署問(wèn)題，證明問(wèn)題難度。接著分別針對(duì)特殊場(chǎng)景和一般場(chǎng)景，設(shè)計(jì)了基于分配問(wèn)題的擴(kuò)展匈牙利算法、基于團(tuán)劃分的Basic算法和基于目標(biāo)Voronoi圖的TV-Greedy算法解決覆蓋問(wèn)題?；谧钚W幾里得樹提出ECST-H算法，解決連通問(wèn)題。理論分析和模擬結(jié)果表明，算法能以較低的時(shí)間和空間復(fù)雜度，用較少的節(jié)點(diǎn)移動(dòng)代價(jià)實(shí)現(xiàn)對(duì)目標(biāo)的覆蓋和全網(wǎng)連通。
　　(3)在WiMAX網(wǎng)絡(luò)中，當(dāng)發(fā)送功率和信道數(shù)目一定時(shí)，用戶接

5、入鏈路的傳輸速率直接取決于用戶到中繼的距離。本文研究如何部署較少中繼，滿足用戶到中繼距離的要求，從而保證用戶的數(shù)據(jù)速率。通過(guò)將該其轉(zhuǎn)化為最少團(tuán)劃分問(wèn)題，基于用戶鄰居信息提出啟發(fā)式算法MAXDCP，接著考慮用戶地理位置信息，設(shè)計(jì)算法GEOCP。理論分析和模擬結(jié)果表明，相對(duì)于已有算法，算法MAXDCP和GEOCP的時(shí)間復(fù)雜度低，能使用更少中繼保證用戶的數(shù)據(jù)速率要求。
　　(4)在移動(dòng)WiMAX網(wǎng)絡(luò)中，用戶在固定中繼的覆蓋區(qū)域之間移動(dòng)，

6、加重了沿途中繼站的負(fù)載，影響信號(hào)中轉(zhuǎn)質(zhì)量。針對(duì)此問(wèn)題，本文提出最少移動(dòng)中繼部署問(wèn)題MMRP，使用移動(dòng)中繼作為臨時(shí)中繼，對(duì)固定中繼進(jìn)行巡邏，減少固定中繼在繁忙時(shí)期的負(fù)載。通過(guò)將MMRP轉(zhuǎn)化為點(diǎn)不相交的最少路徑覆蓋問(wèn)題，分別基于圖的遍歷、最大匹配和最大流思想設(shè)計(jì)算法。理論分析和模擬結(jié)果表明，所提出的算法具有低復(fù)雜度，能夠以較少移動(dòng)中繼滿足對(duì)固定中繼巡邏的要求，有效緩解WiMAX網(wǎng)絡(luò)中固定中繼的負(fù)擔(dān)。
　　綜上所述，本文針對(duì)無(wú)線網(wǎng)絡(luò)中節(jié)