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

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

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

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

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

1調度和通信的復雜性

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

2無錯誤的情況

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

2.1的下限

假設當多個節(jié)點達到最高權重時，任何輸出都是正確的（當q足夠大時，此類事件的概率可以忽略不計）。采用文獻[2]的方法，并使用與其中的節(jié)點廣播的比特序列。[1:q]N中的每個輸入都與廣播歷史關聯(liá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：如果在完成協(xié)議時有沖突的對具有相同的廣播歷史記錄，則調度輸出中將存在錯誤。證明：假設節(jié)點2具有更高的優(yōu)先級，并且兩個節(jié)點都具有相同的廣播歷史記錄。在時隙t上進行歸納，可以證明節(jié)點1將確定其具有最高優(yōu)先級，從而導致調度錯誤?；谝?，獲得了最壞情況下的通信復雜性的下限：命題1：基于優(yōu)先權重比較的調度最壞情況下的通信復雜度由下限來限定：（1）證明：可以將[1:q]N的不同點處的廣播歷史視為顏色。根據引理1，任何沖突的對都不能具有相同的顏色。可以通過得出顏色數量的下限來得出結論。

2.2和的上限

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

3容錯情況

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

3.1下限

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

3.2上限

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

4結語

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

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