導(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ò)

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è)對于數(shù)據(jù)n，q=2n），并且用i表示鏈路i的優(yōu)先權(quán)重。在前同步碼周期中,發(fā)送器廣播其優(yōu)先權(quán)重的部分信息進(jìn)行調(diào)度。其中被確定為具有最高優(yōu)先級的鏈路獲得傳輸權(quán)。假設(shè)前同步碼使用TDMA結(jié)構(gòu)，如圖1所示。對于前導(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è)超級矩形：定義1：如果中的區(qū)域X稱為超矩形，其中是[1：q]的子集。如果f（x）對于所有點(diǎn)x∈X都是相同的，我們將X稱為單色超矩形（相對于f）。容易驗(yàn)證協(xié)議樹的每個(gè)葉節(jié)點(diǎn)是否對應(yīng)于輸入域中的單色超矩形，該矩形的每個(gè)點(diǎn)都導(dǎo)致相同的廣播序列和該給定協(xié)議的最終輸出。分別用L和Rl表示葉子節(jié)點(diǎn)的集合和對應(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)稱為沖突對：（a）這兩個(gè)點(diǎn)的調(diào)度輸出相同，即s表示該函數(shù)；（b）存在j=1或2以及k，使得。示例1：對于N=4和q=8，v1=（4，3，2，1）和v2=（8，7，6，5）是一個(gè)沖突對，此時(shí)。根據(jù)沖突對的定義，證明以下引理：引理1：如果在完成協(xié)議時(shí)有沖突的對具有相同的廣播歷史記錄，則調(diào)度輸出中將存在錯(cuò)誤。證明：假設(shè)節(jié)點(diǎn)2具有更高的優(yōu)先級，并且兩個(gè)節(jié)點(diǎn)都具有相同的廣播歷史記錄。在時(shí)隙t上進(jìn)行歸納，可以證明節(jié)點(diǎn)1將確定其具有最高優(yōu)先級，從而導(dǎo)致調(diào)度錯(cuò)誤。基于引理1，獲得了最壞情況下的通信復(fù)雜性的下限：命題1：基于優(yōu)先權(quán)重比較的調(diào)度最壞情況下的通信復(fù)雜度由下限來限定：（1）證明：可以將[1:q]N的不同點(diǎn)處的廣播歷史視為顏色。根據(jù)引理1，任何沖突的對都不能具有相同的顏色?？梢酝ㄟ^得出顏色數(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è)置和?；睾蟢：如果[ak：bk]之間只有一個(gè)整數(shù)并且|Sk|>1，有兩個(gè)或多個(gè)節(jié)點(diǎn)達(dá)到最高權(quán)重，此時(shí)該算法隨機(jī)選擇一個(gè)鏈接。否則Sk中的所有節(jié)點(diǎn)將按順序廣播。對于節(jié)點(diǎn)j∈Sk，如果，它將廣播1，否則廣播0（是節(jié)點(diǎn)j的權(quán)重）。在所有節(jié)點(diǎn)都完成了第k輪的廣播之后，該算法將采取以下三個(gè)操作之一：（a）如果有多個(gè)節(jié)點(diǎn)廣播1，則設(shè)Sk+1為廣播1的節(jié)點(diǎn)集，設(shè)a，；（b）如果有多個(gè)節(jié)點(diǎn)廣播1，則設(shè)Sk+1為廣播1的節(jié)點(diǎn)集，設(shè)；（c）如果所有節(jié)點(diǎn)都廣播0，則設(shè)以及。當(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)。圖2N=2，q=4時(shí)協(xié)議樹的圖示（2）最壞情況復(fù)雜度：很容易驗(yàn)證最壞情況發(fā)生在（q，q-1…，q-1）4處，其中通信復(fù)雜度由給出，比得出的下限大得多；因此需要縮小差距。（3）平均復(fù)雜度：使用表示該協(xié)議下交換比特的平均數(shù)量。當(dāng)N=2時(shí)，容易驗(yàn)證。這也意味著如果。因此，初始條件意味著。對于通用N，遞歸計(jì)算平均通信位。顯然。假設(shè)權(quán)重分布均勻，對于N個(gè)用戶，第k個(gè)用戶在第一輪保留的概率為滿足下列遞歸不等式：（2）基于公式（2），我們可以得到以下平均復(fù)雜度的上限：命題2：對于任何n和N，都有。

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：對于任何超矩形R，R的差異定義為：，其中P是權(quán)重在中的概率函數(shù)（假設(shè)為統(tǒng)一）。整個(gè)網(wǎng)絡(luò)的差異定義為。顯然，Df為正，因?yàn)閷τ趩蝹€(gè)點(diǎn)，（對于某些情況下的R，Df（R）可能為負(fù)）。與文獻(xiàn)[5]中的提案3.28類似，基于差異的概念，可以得到下限。命題3：對于，通信復(fù)雜度的下限可以表示為：（3）證明：考慮任何復(fù)雜度為且錯(cuò)誤概率小于或等于的協(xié)議，有。通過分析上述不等式中的二進(jìn)制協(xié)議樹和上限概率得出結(jié)論。（2）差異的計(jì)算：以下引理顯示了超級矩形獲得最大差異的必要條件。引理2：如果超矩形R的差異最大，則存在一個(gè)點(diǎn)和一個(gè)i，使得：（4）其中只有第i個(gè)間隔不同，且。證明：假設(shè)R達(dá)到最大差異，并表示為，其中的子集。進(jìn)一步定義和。則有。由于對稱性，假設(shè)i=1，其中i在引理2中定義，而不會失去一般性。當(dāng)N足夠大時(shí)，很難找到達(dá)到最大差異Df的精確超矩形。在考慮組合問題變成連續(xù)問題的漸近情況（即q→∞）。將范圍[1:q]標(biāo)準(zhǔn)化為連續(xù)間隔[0，1]。那么對于滿足的超矩形，差異可以有下列表達(dá)式表示：（5）當(dāng)N=2時(shí)，。通過使微分等于零，最優(yōu)點(diǎn)由和給出。當(dāng)N>2時(shí)，可以通過數(shù)值最大化利用公式（5）來獲得差異。圖3平均通信復(fù)雜度的上限圖4容錯(cuò)調(diào)度程序中的通信復(fù)雜性的下限3.2上限本節(jié)提出了一個(gè)實(shí)用的算法，用于的上限。對于分布式調(diào)度算法，在需要多個(gè)通信位的情況下，可以選擇一個(gè)隨機(jī)鏈路進(jìn)行傳輸。假設(shè)一些常見的隨機(jī)性可用于所有鏈接[3]。則可以用算法1，除了在第一輪比較后有超過k*個(gè)用戶保留時(shí)，協(xié)議停止，并且通過通用隨機(jī)性選擇幸存者中的一個(gè)。顯然k*滿足。該算法通信位數(shù)的平均值的上限：（6）.

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ù)雜度的下限，可以觀察到下限相對于N是非線性的。此外每個(gè)節(jié)點(diǎn)的平均位數(shù)小于1。因?yàn)槟承┕?jié)點(diǎn)發(fā)現(xiàn)自己的優(yōu)先級無法與其他節(jié)點(diǎn)競爭時(shí)它們不會傳輸任何信息。本文使用通信復(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é)院工學(xué)院