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

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

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

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

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

2無錯誤的情況

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

2.1的下限

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

2.2和的上限

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

3容錯情況

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

4結(jié)語

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

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