導(dǎo)語：無線通信網(wǎng)絡(luò)分布式調(diào)度的復(fù)雜性一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：在無線通信網(wǎng)絡(luò)中，調(diào)度通常是以分布式方式進(jìn)行的，并且需要通過無線信道來進(jìn)行信息交換。文章根據(jù)完成調(diào)度所需的通信位數(shù)，研究分布式調(diào)度的通信開銷。并在完整連接圖的特殊情況下，使用通信復(fù)雜性理論來推導(dǎo)相應(yīng)下限，從而提出實(shí)用的廣播協(xié)議來完成分布式調(diào)度。

關(guān)鍵詞：通信復(fù)雜性；分布式調(diào)度；無線通信網(wǎng)絡(luò)

無線通信網(wǎng)絡(luò)中并非所有的節(jié)點(diǎn)都可以同時(shí)傳輸信號(hào)。因此，確定可在干擾限制內(nèi)進(jìn)行傳輸鏈路的調(diào)度非常重要。文獻(xiàn)[6]中提出了多跳網(wǎng)絡(luò)中的調(diào)度策略，該策略實(shí)現(xiàn)了能夠穩(wěn)定數(shù)據(jù)流量的容量區(qū)域（吞吐量最佳）。最近，研究熱點(diǎn)已經(jīng)轉(zhuǎn)移到分布式調(diào)度上，這在adhoc網(wǎng)絡(luò)[7]中更加合理。許多調(diào)度算法都是基于某些優(yōu)先級(jí)權(quán)重的比較。目前大多數(shù)文獻(xiàn)簡單地讓發(fā)射機(jī)廣播其權(quán)重，并允許具有最高優(yōu)先級(jí)的發(fā)射機(jī)進(jìn)行傳輸。但發(fā)送器僅需要知道它們是否具有最高權(quán)重并獲得發(fā)送權(quán)，無需完全了解其他節(jié)點(diǎn)的優(yōu)先權(quán)重，缺乏了分布式調(diào)度最小開銷的研究。在本文中，首先考慮廣播網(wǎng)絡(luò)中基于優(yōu)先級(jí)比較的分布式調(diào)度所需的通信位數(shù)，從而進(jìn)行分布式調(diào)度開銷的研究。并且采用交流復(fù)雜性理論[8]，假設(shè)A有一個(gè)數(shù)字x，而B有另一個(gè)數(shù)字y；A和B需要共同計(jì)算函數(shù)f（x，y）。通信復(fù)雜度定義為在A和B之間對(duì)于計(jì)算f的任何協(xié)議交換的最小位數(shù)。x和y表示優(yōu)先權(quán)重，f（x，y）=I（x≥y）。當(dāng)f（x，y）=1時(shí)，A傳輸;否則B傳輸；此時(shí)假設(shè)在x=y時(shí)，A傳輸。然后，利用通信復(fù)雜性理論中的工具分析調(diào)度的開銷，但也不限于此；其次給出了一些背景知識(shí)。主要研究包括第三節(jié)和第四節(jié)中介紹的無錯(cuò)誤和可容錯(cuò)的案例；最后總結(jié)全文。整篇文章使用以下數(shù)學(xué)符號(hào)：表示向量X的第k個(gè)元素。

1調(diào)度和通信的復(fù)雜性

假設(shè)在無線通信網(wǎng)絡(luò)中有N個(gè)傳輸鏈路，用1，...，N標(biāo)記。在每個(gè)數(shù)據(jù)幀中的數(shù)據(jù)傳輸之前設(shè)置一個(gè)前同步碼周期。每個(gè)發(fā)送器都有一個(gè)整數(shù)值，范圍從1到q（假設(shè)對(duì)于數(shù)據(jù)n，q=2n），并且用i表示鏈路i的優(yōu)先權(quán)重。在前同步碼周期中，發(fā)送器廣播其優(yōu)先權(quán)重的部分信息進(jìn)行調(diào)度。其中被確定為具有最高優(yōu)先級(jí)的鏈路獲得傳輸權(quán)。假設(shè)前同步碼使用TDMA結(jié)構(gòu)，如圖1所示。對(duì)于前導(dǎo)碼和調(diào)度，有以下假設(shè)：（a）沒有從發(fā)送切換到接收或者接收切換到發(fā)射的周轉(zhuǎn)時(shí)間；（b）廣播的順序取決于廣播的歷史記錄（某些節(jié)點(diǎn)可以在整個(gè)過程結(jié)束之前退出廣播）；（c）每個(gè)節(jié)點(diǎn)在一個(gè)時(shí)隙僅廣播一位[2]，具體取決于廣播歷史記錄和該節(jié)點(diǎn)的值；為簡化問題，我們假設(shè)使用開關(guān)鍵控（OOK）；（d）網(wǎng)絡(luò)連接圖完整，這意味著所有節(jié)點(diǎn)都可以解碼所有廣播；（e）權(quán)重{i}在給定范圍內(nèi)均勻分布。定義（優(yōu)先權(quán)重相同時(shí)，隨機(jī)發(fā)送）。本節(jié)研究了分布式計(jì)算函數(shù)f的通信復(fù)雜度，并且考慮了兩種類型的度量標(biāo)準(zhǔn)[3]（關(guān)于所有可能的輸入）：（a）在最壞情況下的最小通信位數(shù)，用表示；（b）用表示通信比特的最小平均數(shù)。如文獻(xiàn)[8]中的兩節(jié)點(diǎn)情況，每個(gè)通信協(xié)議都可以由一個(gè)二叉樹表示，其中每個(gè)葉代表一個(gè)輸出。決策過程等效于從根到葉的遍歷（圖2）。參照兩節(jié)點(diǎn)矩形的概念，在N節(jié)點(diǎn)情況下定義一個(gè)超級(jí)矩形：定義1：如果中的區(qū)域X稱為超矩形，其中是[1：q]的子集。如果f（x）對(duì)于所有點(diǎn)x∈X都是相同的，我們將X稱為單色超矩形（相對(duì)于f）。容易驗(yàn)證協(xié)議樹的每個(gè)葉節(jié)點(diǎn)是否對(duì)應(yīng)于輸入域中的單色超矩形，該矩形的每個(gè)點(diǎn)都導(dǎo)致相同的廣播序列和該給定協(xié)議的最終輸出。分別用L和Rl表示葉子節(jié)點(diǎn)的集合和對(duì)應(yīng)于葉子l的超矩形。

2無錯(cuò)誤的情況

本節(jié)主要研究沒有調(diào)度錯(cuò)誤情況下的通信復(fù)雜性。

2.1的下限

假設(shè)當(dāng)多個(gè)節(jié)點(diǎn)達(dá)到最高權(quán)重時(shí)，任何輸出都是正確的（當(dāng)q足夠大時(shí)，此類事件的概率可以忽略不計(jì)）。采用文獻(xiàn)[2]的方法，并使用與其中的節(jié)點(diǎn)廣播的比特序列。[1:q]N中的每個(gè)輸入都與廣播歷史關(guān)聯(lián)，得到如下定義：定義2：如果[1:q]N中的兩個(gè)點(diǎn)（由v1和v2表示）滿足以下兩個(gè)條件，則將這兩個(gè)點(diǎn)稱為沖突對(duì)：（a）這兩個(gè)點(diǎn)的調(diào)度輸出相同，即s表示該函數(shù)；（b）存在j=1或2以及k，使得。示例1：對(duì)于N=4和q=8，v1=（4，3，2，1）和v2=（8，7，6，5）是一個(gè)沖突對(duì)，此時(shí)。根據(jù)沖突對(duì)的定義，證明以下引理：引理1：如果在完成協(xié)議時(shí)有沖突的對(duì)具有相同的廣播歷史記錄，則調(diào)度輸出中將存在錯(cuò)誤。證明：假設(shè)節(jié)點(diǎn)2具有更高的優(yōu)先級(jí)，并且兩個(gè)節(jié)點(diǎn)都具有相同的廣播歷史記錄。在時(shí)隙t上進(jìn)行歸納，可以證明節(jié)點(diǎn)1將確定其具有最高優(yōu)先級(jí)，從而導(dǎo)致調(diào)度錯(cuò)誤?；谝?，獲得了最壞情況下的通信復(fù)雜性的下限：命題1：基于優(yōu)先權(quán)重比較的調(diào)度最壞情況下的通信復(fù)雜度由下限來限定：（1）證明：可以將[1:q]N的不同點(diǎn)處的廣播歷史視為顏色。根據(jù)引理1，任何沖突的對(duì)都不能具有相同的顏色?？梢酝ㄟ^得出顏色數(shù)量的下限來得出結(jié)論。

2.2和的上限

本節(jié)提出了一種實(shí)現(xiàn)分布式調(diào)度的方案，為通信復(fù)雜性提供了上限。（1）算法：使用二進(jìn)制搜索在[1:q]N中定位一個(gè)點(diǎn)。描述如下：算法1：在整個(gè)過程中更新了兩個(gè)數(shù)據(jù)結(jié)構(gòu)：[ak：bk]表示第k輪的搜索間隔，Sk表示通過先前的比較保留的節(jié)點(diǎn)集?；睾?（初始化）：設(shè)置和。回合k：如果[ak：bk]之間只有一個(gè)整數(shù)并且|Sk|>1，有兩個(gè)或多個(gè)節(jié)點(diǎn)達(dá)到最高權(quán)重，此時(shí)該算法隨機(jī)選擇一個(gè)鏈接。否則Sk中的所有節(jié)點(diǎn)將按順序廣播。對(duì)于節(jié)點(diǎn)j∈Sk，如果，它將廣播1，否則廣播0（是節(jié)點(diǎn)j的權(quán)重）。在所有節(jié)點(diǎn)都完成了第k輪的廣播之后，該算法將采取以下三個(gè)設(shè)a，；（b）如果有多個(gè)節(jié)點(diǎn)廣播1，則設(shè)Sk+1為廣播1的節(jié)點(diǎn)集，當(dāng)N=2且q=4時(shí)，上述算法總結(jié)在圖2的協(xié)議樹中，其中0（1）表示節(jié)點(diǎn)1（2）擁有傳輸權(quán)，如果1=2，假設(shè)節(jié)點(diǎn)2擁有傳輸權(quán)。（2）最壞情況復(fù)雜度：很容易驗(yàn)證最壞情況發(fā)生在（q，q-1…，q-1）4處，其中通信復(fù)雜度由給出，比得出的下限大得多；因此需要縮小差距。

3容錯(cuò)情況

調(diào)度錯(cuò)誤的概率很小，可以用僅降低邊際性能為代價(jià)，大大降低通信的復(fù)雜性，因此該研究允許調(diào)度錯(cuò)誤的情況。當(dāng)可容忍的錯(cuò)誤概率為時(shí)，用表示最壞情況的最小通信位數(shù)，用P（x）表示點(diǎn)x處的容錯(cuò)協(xié)議的輸出，可能不同于f（x）。

3.1下限

關(guān)于的下限。（1）基于差異的下限：在這種情況下，使用文獻(xiàn)[5]中的差異方法來獲得通信復(fù)雜性的下限。定義3：對(duì)于任何超矩形R，R的差異定義為：，其中P是與文獻(xiàn)[5]中的提案3.28類似，基于差異的概念，可以得到下限。

3.2上限

本節(jié)提出了一個(gè)實(shí)用的算法，用于的上限。對(duì)于分布式調(diào)度算法，在需要多個(gè)通信位的情況下，可以選擇一個(gè)隨機(jī)鏈路進(jìn)行傳輸。假設(shè)一些常見的隨機(jī)性可用于所有鏈接[3]。則可以用算法1，除了在第一輪比較后有超過k*個(gè)用戶保留時(shí)，協(xié)議停止，并且通過通用隨機(jī)性選擇幸存者中的一個(gè)。

4結(jié)語

圖3顯示了在無錯(cuò)誤和可容錯(cuò)（=0.1）的情況下從公式（2）和（6）中的遞歸不等式獲得的。可以觀察到，在N中幾乎線性增加，而在n中增加緩慢，根據(jù)觀察，當(dāng)允許某些調(diào)度錯(cuò)誤時(shí)，可以大大減少所需的通信開銷。圖4顯示了在可容許的錯(cuò)誤概率（0.05或0.15）下，根據(jù)提案3中的差異方法獲得的最壞情況下的通信復(fù)雜度的下限，可以觀察到下限相對(duì)于N是非線性的。此外每個(gè)節(jié)點(diǎn)的平均位數(shù)小于1。因?yàn)槟承┕?jié)點(diǎn)發(fā)現(xiàn)自己的優(yōu)先級(jí)無法與其他節(jié)點(diǎn)競爭時(shí)它們不會(huì)傳輸任何信息。本文使用通信復(fù)雜性理論分析了無線網(wǎng)絡(luò)中分布式調(diào)度所需的通信位數(shù)。當(dāng)調(diào)度基于優(yōu)先權(quán)重比較并且網(wǎng)絡(luò)具有完整的連接圖時(shí)，研究得到了上限和下限。但仍然存在許多未解決的問題，如任意網(wǎng)絡(luò)拓?fù)?、通用調(diào)度協(xié)議以及周轉(zhuǎn)時(shí)間的影響。

作者：左晨微 單位：鄭州工商學(xué)院