無(wú)線(xiàn)網(wǎng)絡(luò)中控制集構(gòu)造算法的研究.pdf

1、近年來(lái)，隨著無(wú)線(xiàn)通信技術(shù)與設(shè)備的發(fā)展，無(wú)線(xiàn)網(wǎng)絡(luò)在各種領(lǐng)域得到了廣泛應(yīng)用。無(wú)線(xiàn)設(shè)備使用局部廣播的方式進(jìn)行彼此之間的通信造成了網(wǎng)絡(luò)中大量信息的冗余與能量的浪費(fèi)。如何減少網(wǎng)絡(luò)中信息的冗余、節(jié)約能量是無(wú)線(xiàn)網(wǎng)絡(luò)協(xié)議設(shè)計(jì)過(guò)程必需要考慮的問(wèn)題。從某種意義上來(lái)說(shuō)這一問(wèn)題決定了無(wú)線(xiàn)網(wǎng)絡(luò)的服務(wù)質(zhì)量，而拓?fù)淇刂颇軌蚪鉀Q上述問(wèn)題，因此設(shè)計(jì)有效的拓?fù)淇刂茀f(xié)議是十分必要的。所謂拓?fù)淇刂疲侵冈跓o(wú)線(xiàn)網(wǎng)絡(luò)相應(yīng)的圖模型中構(gòu)造具有某些特殊性質(zhì)（如，連通性、稀疏性、低干擾等

2、）的子圖?？刂萍峭?fù)淇刂浦械囊环N重要的方法，在無(wú)線(xiàn)網(wǎng)絡(luò)中得到了廣泛研究。
　　本文通過(guò)對(duì)現(xiàn)有控制集算法的研究與分析，首先在beep模型下提出了BMDS、BCDS算法。離散beep模型是一個(gè)極其嚴(yán)格的局部廣播模型，該模型僅依賴(lài)載波偵聽(tīng)，網(wǎng)絡(luò)中的節(jié)點(diǎn)不需要任何先驗(yàn)信息，例如節(jié)點(diǎn)的唯一標(biāo)識(shí)符，網(wǎng)絡(luò)的拓?fù)湫畔⒌?。然后，在SINR模型下設(shè)計(jì)了DSS_MIS與DSS_CDS算法。SINR(Signal-to-Interference-plu

3、s-Noise-Ratio)模型是一個(gè)更加切合實(shí)際的累積干擾模型。事實(shí)上，我們還通過(guò)理論分析分別證明了它們的有效性與正確性。
　　本文共分為五章。第1章介紹了研究的背景、意義與研究現(xiàn)狀。第2章對(duì)當(dāng)前存在的一些控制集算法進(jìn)行了分類(lèi)與總結(jié)，并對(duì)某些經(jīng)典的控制集構(gòu)造協(xié)議進(jìn)行了分析。第3章首先給出了離散beep模型下的一個(gè)分布式最小控制集的近似算法（Beeping a Minimum Dominating Set，BMDS），該算法是一個(gè)

4、基于局部控制度（節(jié)點(diǎn)的非受控鄰接點(diǎn)的數(shù)目）的貪心選擇策略，然后設(shè)計(jì)了beep模型下的極大獨(dú)立集構(gòu)造算法以及弱連通控制集構(gòu)造算法，基于上述兩種算法，提出了beep模型下的連通控制集構(gòu)造算法（Beeping a Connected Dominating Set，BCDS）。最后利用節(jié)點(diǎn)間的沖突提出了另一個(gè)連通控制集的構(gòu)造算法（Beeping a Connected Dominating Set with Collision，BCDSC）。在

5、一個(gè)自穩(wěn)定的系統(tǒng)是指具有錯(cuò)誤容忍能力的系統(tǒng)，即能夠承受發(fā)生的錯(cuò)誤，并且在沒(méi)有外力干擾的情況下從這些短暫的錯(cuò)誤中恢復(fù)過(guò)來(lái)。由于無(wú)線(xiàn)網(wǎng)絡(luò)面臨著復(fù)雜的工作環(huán)境，其拓?fù)渥兓瘯r(shí)常發(fā)生變化，所以自穩(wěn)定性是無(wú)線(xiàn)網(wǎng)絡(luò)協(xié)議設(shè)計(jì)過(guò)程中必要選擇。為了保證這些自穩(wěn)定算法能夠在實(shí)際網(wǎng)絡(luò)中應(yīng)用，還必須在協(xié)議的設(shè)計(jì)過(guò)程中考慮干擾因素。第4章解決了自穩(wěn)定性與干擾的問(wèn)題，基于分區(qū)與著色的思想，首先在SINR模型下提出了分布式自穩(wěn)定的極大獨(dú)立集構(gòu)造算法（ Distribu

6、ted Self-Stabilizing Maximal Independent Set construction algorithm，DSS_MIS），然后在概算法的基礎(chǔ)上進(jìn)行改進(jìn)最終得到了分布式自穩(wěn)定的連通控制集構(gòu)造算法（ Distributed Self-Stabilizing Connected Dominating Set construction algorithm，DSS_CDS）。第5章對(duì)本文進(jìn)行了總結(jié)，并對(duì)未來(lái)進(jìn)一步的