物理干擾模型下的無線鏈路調(diào)度.pdf

1、無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)是一種飛速發(fā)展的新興網(wǎng)絡(luò),是將傳感器節(jié)點隨機部署在指定區(qū)域并自組織成的無線多跳通信網(wǎng)絡(luò)。WSNs綜合了傳感、信息處理和嵌入式等多項技術(shù),可以對部署區(qū)域內(nèi)感興趣的信息進(jìn)行協(xié)作地感知、采集和處理,并采用已經(jīng)形成的多跳路徑將獲取到的信息最終傳遞到基站?；就ㄟ^互聯(lián)網(wǎng)或衛(wèi)星通信將信息傳遞給用戶進(jìn)行分析。作為本世紀(jì)十大科技之一,WSNs在許多方面都展現(xiàn)了廣泛的應(yīng)用前景,

2、有些方面甚至已經(jīng)得到大量應(yīng)用。
　　雖然 WSNs在許多領(lǐng)域已經(jīng)取得了一系列成就,但作為新興的高科技技術(shù),WSNs領(lǐng)域仍有很多開放性問題需要解決,例如鏈路調(diào)度,拓?fù)淇刂?控制集的構(gòu)造,嵌入和時間同步等。本文就 WSNs中的鏈路調(diào)度問題進(jìn)行了分析與研究。
　　本文對調(diào)度問題的已有研究成果進(jìn)行了詳細(xì)的描述,并在物理干擾模型下提出了最大權(quán)重獨立集(Maximum Weighted Independent Set of Links,

3、 MWISL)問題的啟發(fā)式算法、最短鏈路調(diào)度(Shortest Link Scheduling, SLS)問題的常數(shù)近似算法和最小延遲數(shù)據(jù)聚合(Minimum Delay Data Aggregation, MDDA)問題的近似算法。對于每個算法,我們都對算法的正確性給予理論分析,并通過仿真對算法的有效性進(jìn)行了驗證。具體研究內(nèi)容如下:
　　MWISL問題可以描述為給定一組通信鏈路,每一條鏈路都有一個權(quán)重,根據(jù)干擾約束條件選擇一個能

4、夠同時進(jìn)行信息傳輸?shù)逆溌纷蛹⑶沂沟迷摷现兴墟溌返臋?quán)重之和最大。MWISL問題的啟發(fā)式算法每次采用貪婪策略從候選鏈路集合中選擇一個滿足條件的最優(yōu)鏈路。依次執(zhí)行,直到所有候選鏈路處理完成。仿真實驗表明,算法具有良好的實際性能。
　　SLS問題的目標(biāo)是在給定的約束條件下,以最短的時間調(diào)度所有鏈路。在有界線性功率分配方式下,提出了一個 SLS問題的常數(shù)近似算法。采用網(wǎng)格劃分的方法,使得每個時間段所對應(yīng)的鏈路集合中的鏈路都滿足 SIN