無線通信網絡分布式調度的復雜性

導語：無線通信網絡分布式調度的復雜性一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

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

關鍵詞：通信復雜性；分布式調度；無線通信網絡

1調度和通信的復雜性

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

2無錯誤的情況

本節主要研究沒有調度錯誤情況下的通信復雜性。

2.1的下限

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

2.2和的上限

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

3容錯情況

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

4結語

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

作者：左晨微 單位：鄭州工商學院工學院