1、伴隨有限帶寬和時變拓撲結構的數字網絡下的分布一致性摘要在這篇文章里，我們考慮了離散時間下伴有有限通信傳輸率和時變通信拓撲結構的分布平均一致性。我們基于進位制改革的量化設計了一個分布式編碼解碼方案，并且在對稱補償方法的基礎上設計了一個控制協議。我們提出了一個自適應方案，根據關聯信道的活躍與否來選擇量化水平的數量。我們證明了，如果網絡是共同連接的，那么在協議設計下，平均一致性能漸進地實現，并且收斂速率被量化。尤其是，如果網絡中的任何的連接失敗的寬度是有界的，那么控制參數和尺度函數可以被恰當的選取出來，如此一來5級量化器對于指數漸進速率下的漸進平均一致性來說足夠了。關鍵詞：多代理商系統 分布式一致

2、數據傳輸率 量化 時變拓撲結構引文在最近幾年，多代理商網絡上的分布式協作已經成為網絡控制系統和復雜性科學的最具活力的一個方向之一。當開始采用數字通信，因為有限的信道容量，每個時間步只有很有限的一小部分的信息能在鄰級代理商進行交換。在鄰級代理商的通信是編碼，傳送，接收，解碼的綜合過程。與傳統的單一控制理論相似的是，這個基于由無限開始的多代理商協作的研究沒有考慮通信約束，隨著深入的研究，研究員漸漸地開始注意通信網絡的各個方面。最近，量化一致性或者是量化通信的一致性引起了越來越多的研究人員的注意。大多數現存的關于量化通信分布一致性研究都假定非時變的通信拓撲結構。眾所周知，由于許多像聯結失敗或環境改變

3、這類的原因，多代理商網絡下的通信拓撲經常是時變的。由于聯結失敗引起的網絡拓撲結構的改變是一種無源開關。一個好的分布式一致算法需要具備穩健性來對抗這種開關。在某些其他案例里，網絡的拓撲結構可能會被有目的的改變，比如說，根據為了整個系統的性能優化的高級命令而選取的不同模式的網絡交換機。因為有限的帶寬，量化通信和時變拓撲結構下的分布式一致在理論和工程上的觀點來說都具有意義。Dimarogonas 和 Johansson 思考了靜態無限層次均化和邏輯量化器的量子化的相對狀態信息下的分布式一致，并且證明了如果在切換點之間，對于所有的連續時間間隔通信圖都保持樹，假若量化密度足夠的高，那么一致性可以實現。N

4、edic,Olshevsky,Ozdaglar,和Tsitsiklis思考了時變拓撲結構和靜態無限層次均化量化器下的量化平均一致性。他們證明了如果通信圖是共同連接的，那么近似平均一致性是可以實現的。Carli et al.，Lavaei和Murray考慮了一個基于一個無限級數一致的量化器的量化通信的隨機流言算法。Carli et al.（2009a,b）。Kar和Moura(2009)考慮了用靜態無窮級和有限級一致的量化器的有著隨即連接失敗的量化平均一致性。他們在在量化之前添加了一個隨機抖動來制造一個量化誤差白噪音和證明了如果如果拉普拉斯矩陣序列是i.i.d并且這意味著圖總是連通的，然后所有的

5、代理商的狀態值最終以極高的可能性進入內部狀態平均值的小鄰級代理商。注意到以上文獻集中在靜態無窮層次量化器和穩態誤差不是零。在這篇論文里，我們考慮了伴隨有限通信帶寬的離散時間下的平均一致性。代理商有實值狀態和在無向數字網絡下彼此之間的通信。網絡拓撲可以是時變的。這里存在兩個最基本的問題。一個是代理商之間的信道是有限容量的，因此只有有限級的量化器可以被使用，這可能導致無界的量化誤差。另一個是對于給定的代理商的鄰級代理商可能隨著時間發生改變，這可能導致為合適的拓撲情況（Li et al.,2011）設計的編碼解碼方案之間的不協調。為了克服這些困難，我們設計了一個基于比例創新量化器的分布式編碼解碼方案

6、，其中擴展函數是用來避免有限層次量化器的飽和。在這里，不像確定拓撲結構的那種情況，每個信道都有自己的編碼器解碼器。每個量化器的量化電平的數值由相關聯信道的狀態決定。我們提出一個基于對稱補償的控制協議并且設計了一個合適的方案來選取量化電平的數值。每個量化器的量化電平的數值是根據相關信道在上一步是否活躍而調好的在線數據。通過使用這個方案，我們證明了如果網絡是共同連接的，那么在設計的協議下，平均一致性可以沒有穩態誤差的漸進實現，這就意味著平均一致性隨著時間的推移以任意精度被實現。我們表明收斂速率不比擴展函數低。尤其是，如果任何網絡中的連接失敗的持續時間都是有界的，那么控制增益和擴展函數可以被適當的設

7、置使得對于以指數形式收斂的漸進平均一致性5級量化器也已經足夠。這篇論文接下來的部分是這樣的。在第2部分，我們提出了網絡的模型和公式化問題來進行研究。在第3部分，我們提出了編碼解碼方案和一個控制協議。在第4部分，我們研究了怎樣設置控制參數來確保漸進平均一致性并且為閉路循環系統給出收斂速率。在第5部分，我們給出了數例來論證我們協議的有效性。在第6部分，給出了某些結論和提出了未來的研究課題。下列符號將會在這篇論文中用到：1表示一元素全為1的列向量。I表示一個合適大小的單位矩陣。對于給定的s，表示元素的數量，給出一個向量或是矩陣A，它的轉置陣以表示，它的無窮范數用表示，它的歐幾里得范數用表示。對于一個

8、給定的正數x，它的自然對數為它以二為底的對數形式為，小于或等于x的最大整數值記為，大于或等于x的最小整數值記為。對于兩個實對稱矩陣A和B，我們定義如果A-B是半正定的，那么.2.模型描述和問題公式化我們考慮了一個有N個代理商的網絡的動態分析，其中分別是第i個代理商時間為t時的狀態值和輸入值。代理商之間的通信由無向圖表示，其中是一組節點，是的鄰接矩陣的權重，其中用來表明從j到i是否活躍的通信渠道。由于通信圖是無向圖，所以是一個對稱矩陣，在時間t下第i個代理商的相鄰代理商由定義。的基數被叫做i在時間t時的度，并且用表示。定義的拉普拉斯矩陣由定義，其中我們用數對來表示從j到i的通信渠道。活躍通信渠道

9、的一個有序數對被叫做從代理商到代理商的路徑。如果對于任意的都有從i 到j的路徑，那么圖就叫做連通圖。對于一序列我們有下列的假設備注1.我們注意到代表第i個代理商的一組無窮多的鄰級代理商。假設意味著如果第j個代理商在某一個時刻是i代理商的鄰級代理商，那么在時間趨于無窮時它也是i代理商的鄰級代理商。注意那些渠道只在有限期里不會對協議設計和閉環管理產生本質上影響的時候存在。在這篇論文里，我們目標是設計一個使用數據的有限比特位的編碼解碼方案和一個交互協議來實現漸進平均一致性。3.協議設計我們假設在代理商之間只有具有象征意義的數據才能進行交換。對于每個通信渠道，傳輸器的狀態值首先對代表數據進行編碼然后進

10、行傳輸，之后數據被接收，接收器使用的解碼器得到一個傳送器狀態的估計值。對于代理商i和代理商j，其中對于信道，第i個代理商的編碼器是按以下設計的 其中是的內部狀態，和分別是的輸入值和輸出值。在這里是一個量化器，并且是一個拓展函數。對于代理商，信道將是永遠不會活躍的，對于信渠設計一個編碼器它是無關緊要的。因此，總體上看有個 編碼器是與代理商i有關聯的。對于信道代理商j有關聯的解碼器由以下給出其中是的輸出值。當信道是活躍的，在被代理商j接收之后，解碼器被激活來獲得的估計值。備注2.眾所周知，對于分布式一致性使用動態編碼解碼方案這個思想是由Carli et al.首次提出的。在這里，編碼器（2）和解碼

11、器（3）的結構和那些之前（Carli和Bullo,2009;Carli et al.2010a;Li et al.，2011）里的是一樣的，然而，由于通信拓撲的時變性，這里有兩個主要不同點。對于確定通信拓撲結構的情況，更新增益和編碼器的數字轉換器都是確定的，對于時變拓撲結構的情況，編碼器和解碼器的參數，比如和的量化電平的數值都是對于信道合適選取的。對于確定通信拓撲結構的情況，每個代理商都只需要堅持一個編碼器，對于時變拓撲結構的情況，因為鄰級代理商的狀態的鏈接是隨時間變化的，我們需要為第i個代理商設計個編碼器。備注3.由上可知，要計算在時間t時編碼器和解碼器的輸出值，需要同時知道代理商i和代理商

12、j的，也就是說，它們之間的的信道是否活躍。我們注意到如果通信拓撲的開關是預先知道的，那么很明顯也就知道了，并且如果信道的值不能優先知道，比如間歇性的鏈接失敗或者是數據包丟失的情況，那么我們可以使用一個分離的反饋信道來知道。這個反饋渠道假設是可靠的并且在鄰級的代理商間的每個反饋將會花費信息傳送的一個比特位。我們采用了有限層次的統一的對稱量化器，也就是，量化器采取以下的形式其中K可能隨著時間改變。對于是2K+1級量化器。備注4.在確定的拓撲結構的情況下，我們假定量化器的輸出值0不會被傳送，并且量化器的比特值是。在這里，為了避免與閑置信道的情況混淆，輸出值0將會明確地傳送給鄰級代理商，因此量化器的比

13、特值為。我們用由時間決定的來表示的量化電平數值，并且提出了如下的分布式協議其中控制參數h>0。定義從接下來的定理里我們可以知道協議（2），（3）和（5）能保存閉路循環系統的平均狀態。定理3.1.如果假設（A1）成立，那么在協議（2），（3）和（5）下，閉路循環系統滿足證明.從（2），（3）可以知道然后由的定義和協議（5），我們知道通過假設（A1），我們知道了此外，當且僅當很容易就可以得到然后和（1）一起推出（6）。備注5.我們注意到可以把控制輸入（5）可以分為和誤差補償項因為在編碼解碼過程中信息的丟失，控制輸入偏離了by對于鄰級代理商的狀態值的估計誤差的權重和。從對于定理3.1的證明來看

14、，可以知道估計誤差和可以由補償，這項只是關于鄰級代理商的誤差補償的權重和。最關鍵的思想是對于每個信道，雖然通過代理商i接收誤差是不知道的，發送誤差可以用減去代理商i本身的編碼器的內部狀態值得到。因此，代理商i可以對代理商j基于發送誤差的接收誤差作出補償。由于整個網絡的對稱性，全部接收誤差的和可以被補償而且系統的平均值被保存下來。4.收斂分析我們做出了如下假設：（A2）這有一個常數>0，如此以致（A3），其中和已知是非負常數。（A4）存在一個整數T>0和一個實常數>0，使得,其中為拉普拉斯矩陣的第二最小算子。備注6.當且僅當存在整數和常數時，假設（A4）成立，使得這就意味著網絡

15、流量在間隔是共同連接并且平均代數連通性一致的下界趨近于零。比如，如果有限數量圖中的網絡交換機是基于有界的連續不斷的間隔中共同連接，那么（A4）成立。如果假設（A4）成立而且那么是可以證明的。令和。從（2），（3）和（5）我們可以看見我們的協議可以由以下參數表征：控制增益h，量化電平的數值和拓展函數，我們可以考慮如何選取控制參數來確保漸進平均一致性。在下面的定理中，我們可以發現對于任意給定的控制增益h和拓展函數，每個信道的量化電平的數值可以由以下步驟合適選取出來：如果在時間t時信道是活躍的，那么在時間t+1的量化電平的數值可以維持為一常數，如果信道不是活躍的，或是存在聯結失敗，那么量化器的量化電

16、平的數值為了這個信道會被增強，這樣因為聯結失敗導致的不確定性就通過提高信息準確度抵消了。關鍵點在于通過選取設計參數來令量化器是非飽和的。定理4.1假定假設（A1）（A4）成立。如果，,并且對于任意的，量化電平的數值滿足其中然后在協議（2），（3）和（5）下，閉路循環系統滿足不只如此，如果那么定理4.1的證明需要閉路循環一致性誤差補償的細節分析。把協議（2），（3）和（5）代入系統（1）。閉路循環系統由給出定義其中當時，定義為0。閉路循環系統（13）又可以寫成向量形式然后有上述公式和的定義，當我們得到可以由它得出一致性誤差Eq.（14）有以下特性1 均勻部分的狀態矩陣是單位矩陣減去一個時變拉普拉

17、斯矩陣。2 和總為0.因為狀態矩陣是時變的，在固定拓撲結構情況下使用的對角化方法不再合適。然而，通過結合上述特性，拉普拉斯圖的屬性和分析線性時變系統的方法，我們研究了引理4.1和4.2來得到一致性誤差，控制參數，網絡流量的參數和之間的關系。引理4.1.令成為無向圖的拉普拉斯矩陣的一組序列，對于任意的整數滿足定義對于給定的假設是一個向量滿足和令然后且引理4.2 假設當那么不僅如此，如果那么引理4.1的證明。從（2），我們得出由此式和的定義，我們得出，這個式子和（13）得出由以上和（21），我們可以知道如果那么如果，那么僅當由（5）我們可以知道然后通過假設（A3）和（7），它遵循下列條件和（2）可

18、以一起推出相似的，由假設(A2)(A3)，(8)和(23)(26)，我們可以得到定義從我們知道我們注意到對于任意的N維向量x，然后由（15），假設（A4）和引理4.1，我們可以得到這個和得出定義是下面方程的解定義，然后由（29）我們得到從我們得到，然后由（30），假設（A2）和引理4.2，我們可以得到這個和（28）可以得出結合上述方程和（23），（24）和假設（A2），我們得到如果，那么如果那么現在我們證明了如果對于所有的k=0,1,.,t-1,t=2,3,.,那么。假設。如果，那么通過（9）和（32）。我們得到同時相似的，如果，那么由（9）和（33）。我們得到這個和（34）一起推出，然后由（

19、26），（27）和引文，我們總結出從我們可以得出從（30）和引理4.2，我們，這個和（28），（35）和（36）推導出（11）。如果然后由（11）和定理3.1，我們可以得出（12）。備注7.從（21）（22）和的定義，可以看出全局閉路循環系統實質上是由來描述的一個非線性系統。在這里，是由構成的內部狀態向量，是由構成的量化器誤差向量。是基于有限層次量化器非線性的一個離散非線性時變向量函數。這種系統包括一個在一致性誤差和量化誤差之間的非線性交互作用。為了分析（37）描述的系統，首先，由（14）引理4.1和4.2，我們得到一個不等式描述一致性誤差是怎樣被影響支配的。其次我們將（31）代入（23）和（

20、24）來得到量化誤差的上界。最后，反過來我們把這個上界值帶入到（14）然后得到一個一致性誤差的估計值。這個處理一致性誤差和量化誤差之間的非線性相互作用的方法和那個分析自適應控制系統的算法（過去用來處理系統狀態和辨識誤差之間的非線性交互作用）在精神上是相似的。備注8.常數和反映了在某些情況下拓展函數的收斂屬性。如果那么。通過定理4.1，我們可以看見（11）給出了一個閉路循環系統的恒定不變的誤差值：。如果，那么恒定不變的誤差值為0而且（11）給出這個閉路循環系統的收斂速率：。備注9.從定理4.1，我們知道為了實現漸進平均一致性，我們可以設置拓展函數隨著時間的增加而消逝。比如，在這種情況下，和一致性

21、可以以指數形式快速達成。另一個方法是設置。這種情況，一致性會相對慢些，然后，因為，僅僅從（9）來看，在一種漸進情況下量化電平的數值可能會減少。在情形1里提及的，鏈接失敗和補償或在通信網絡里的數據包丟失可以以網絡拓撲的交換。在時間t信道的連接失敗暗示這，否則。注意到伴隨著有限數據包丟失的單代理商網絡控制系統的控制問題已經被廣泛進行了研究。在下面，我們可以看見如果網絡中的任意連接失敗的持續時間是有界的，那么可以選取一個為常數的量化電平的數值。尤其是，控制增益和拓展函數可以被合適的設置以致5層次的量化器（K=2）對于以指數收斂速率收斂的漸進平均一致性已經足夠。對于任意，定義在t時由得到。我們需要接下

22、來的假設。（A5）存在一個整數，使得在這里，被調到零。備注10.上述的內容定義了對于信道的第k次失敗的開始時間，同時定義了對于信道的第k次補償的開始時間，表示了信道的第k次失敗的持續時間。可以看見假設（A5）意味著所有鏈接失敗的持續時間都是有界的。備注11.假設g是沒有鏈接失敗的連通圖。因為連接失敗，網絡拓撲在時間t的成為一個g的子圖。如果連接失敗的補償是以一個正整數來表示邊界，然后假設（A4）和（A5）隨著都成立，這里L是g的拉普拉斯矩陣。定理4.2.假定假設（A1）（A5）成立。對于任意整數,定義然后（i）是非空的。（ii）對于任意的h和都使得和在協議（2），（3）和（5）下和量化電平數值

23、滿足閉路循環系統滿足證明.對于任意的整數，從（10），我們得到和，這意味著這里存在使得注意到從（42）和（43），我們知道了存在使得,這樣（i）成立。對于任意滿足的h和，我們有。由（38）和（40），我們得出（7）。由（39），（40）和（41），我們得出（8）。然后與定理4.1相似的，我們得到了（26）和（27）。現在我們證明了如果，對于所有的都有。假設。由（40），（41）假設（A5）和的定義，與（32）相似的，我們可以得到由（44），和（33）相似，我們得到結合（44）和（45），我們得到然后與定理4.1相似的，我們可以得出（ii）成立。在上述的定理中，提到了K可以被設置為1，然后從（4

24、0）和（41），我們可以看出5層次的量化器可以通過合適的設定控制參數來確保漸進平均一致性。備注12.在Li et al.(2011)，我們證明了對于一個聯結的網絡，漸進平均一致性通過用以3層次（單比特）的量化器總是可以實現。在這里，從定理4.2和備注13，我們可以看出在一個有著間歇鏈接失敗或數據包丟失的連通網絡，提供了持續期是有界的，5層次（3比特）量化器足夠用于漸進一致性。另外的2層是用來補償因為連接失敗或數據包丟失帶來的信息丟失。備注13.從定理4.2，我們可以看見控制參數h和因為某些全球網絡拓撲信息N,和T的需求而被設計為不實時的。使得存在不需要基于全球信息的離線設計參數的靜態無限層次的

25、量化器的一致性算法，就像Kashyap et al.(2007)和Lavaei，Murray(2009a),在將來為了動態有限層次量化器的分布式一致性設計的實時參數算法是十分有趣的。備注14.在這篇論文里，我們假設通信網絡是無向的。對于將來的研究，研究關于有向拓撲的情況將是十分有趣的。主要的困難可能包括對稱補償方法的失敗和在引理4.1里的技術。可能需要開發新的補償和閉路循環分析的方法。5. 數例在這個情景，我們用了一個數例來論證我們協議的有效性。我們考慮了一個三個代理商切換拓撲的網絡其中可以看出，這里。控制參數h為0.01和拓展函數為。所以。根據定理4.1，量化電平的數值如下設置：如果或者如果狀態的演變和在Fig.1中展現出來了。可以看見平均一致性是可以被漸進實現的。可知定理4.1的結果通常是穩定的，更少的量化電平會被使用并且在這個例子中收斂速率是可以提升的。我們選取h=0.2，。