無(wú)線網(wǎng)絡(luò)中基于SINR的分布式染色算法的研究.pdf

1、空間資源復(fù)用是無(wú)線網(wǎng)絡(luò)的關(guān)鍵特征，空間資源復(fù)用在提高網(wǎng)絡(luò)容量的同時(shí)，也引起了公共信道沖突，這被認(rèn)為是無(wú)線通信性能下降的一個(gè)主要原因。沖突的本質(zhì)是干擾，干擾建模是量化干擾的通用方法。分布式理論在無(wú)線傳感器網(wǎng)絡(luò)中有著廣泛的應(yīng)用，無(wú)線網(wǎng)絡(luò)中的許多問(wèn)題都是分布式算法設(shè)計(jì)中需要面對(duì)的經(jīng)典問(wèn)題。染色問(wèn)題在實(shí)際生活中有著廣泛的應(yīng)用，不僅是無(wú)線網(wǎng)絡(luò)中是一些MAC協(xié)議設(shè)計(jì)的基礎(chǔ)，也是分布式計(jì)算中打破對(duì)稱的一個(gè)主要方法。
　　分布式理論的一些問(wèn)題具有

2、一定難度，容易產(chǎn)生的一個(gè)錯(cuò)覺(jué)是理論與實(shí)際應(yīng)用之間存在較大斷層，即理論上很成熟，但是實(shí)際應(yīng)用中又比較抽象。論文從應(yīng)用的角度探究分布式理論在無(wú)線傳感器網(wǎng)絡(luò)算法設(shè)計(jì)中出現(xiàn)的經(jīng)典問(wèn)題，并對(duì)一些經(jīng)典問(wèn)題之間的關(guān)系進(jìn)行了討論，例如獨(dú)立集和染色之間、獨(dú)立集和支配集之間等。
　　目前主要存在沖突圖（Conflict Graph,CG）模型、一般圖（General Graph,GG）模型、協(xié)議干擾模型（Protocol Interference M

3、odel,PM）和物理干擾模型（Signal to Interference Plus Noise,SINR）等各類干擾模型，這些模型各有優(yōu)缺點(diǎn)。論文通過(guò)干擾建模對(duì)SINR模型進(jìn)行擴(kuò)展，使得一些CG模型或者PM能夠更好的描述實(shí)際情況。最后，在擴(kuò)展后的SINR模型下，利用弱圖染色的思想，設(shè)計(jì)染色算法。具體研究?jī)?nèi)容如下：
　　在各類干擾模型中，物理干擾模型能夠更好的描述實(shí)際情況，2-distance沖突圖模型能夠更好地限制干擾，但是只

4、能模型化兩個(gè)并發(fā)傳輸?shù)母蓴_。累積所有并發(fā)傳輸?shù)母蓴_，并以此為依據(jù)建立規(guī)劃函數(shù)，將2-distance沖突模型轉(zhuǎn)化為SINR。論文總結(jié)了將沖突圖模型轉(zhuǎn)化到SINR模型的一般過(guò)程，通過(guò)選擇合適的因子實(shí)現(xiàn)σ模型向標(biāo)準(zhǔn)2-distance的轉(zhuǎn)化，通過(guò)公式推導(dǎo)將以接收節(jié)點(diǎn)為中心的PM模型轉(zhuǎn)化為σ-協(xié)議模型，以發(fā)送節(jié)點(diǎn)為中心的PM模型轉(zhuǎn)化為σ-Tx協(xié)議模型，從而達(dá)到PM模型向SINR模型的轉(zhuǎn)化。
　　染色問(wèn)題在不同的干擾通信模型下有很多不同的

5、解決方案，在深入研究染色問(wèn)題之后，結(jié)合缺陷染色和部分正常染色的思想，在SINR模型下得到一個(gè)(Δ+1)-染色分布式算法。假設(shè)圖最初弱染色，并且每一個(gè)節(jié)點(diǎn)有一個(gè)不一樣的頂點(diǎn)標(biāo)識(shí)符。首先計(jì)算一個(gè)極大獨(dú)立集（Maximal Independent Set, MIS），算法的時(shí)間復(fù)雜度為O(log n)；然后通過(guò)時(shí)間復(fù)雜度為O(Δ)的K-部分正常染色算法和時(shí)間復(fù)雜度為O(logΔ)的D-缺陷染色算法得到(Δ+1)-染色，其中K<Δ，最終算法的時(shí)