陸璐璐 卜 禹

（江蘇科技大學計算機學院 鎮(zhèn)江 212000）

1 引言

隨著人工智能的發(fā)展，多智能體系統(tǒng)（Multi-Agent System，MAS）已經(jīng)成為分布式人工智能領域的重要研究方向之一［1］。MAS 是多個智能體組成的集合，旨在通過智能體間的通信進行信息的共享，實現(xiàn)多個智能體間的協(xié)同與合作，完成單個智能體所無法完成的復雜任務。相比于單個智能體來說，MAS 顯現(xiàn)出更好的魯棒性和靈活性。當多個智能體組成MAS 之后，智能體與智能體之間就會產(chǎn)生所謂的通信問題。在多智能體中，狀態(tài)分享、信息交換、任務協(xié)作都離不開通信，因此，智能體間通信的優(yōu)劣直接影響著整個系統(tǒng)的效率。

在多智能體的通信過程中，在物理層完成頻譜的感知和調(diào)制后，鏈路層以及上層所面對的最基礎的網(wǎng)絡資源便是無線信道［2］。在MAS 的通信網(wǎng)絡中存在多個信道，利用多信道進行數(shù)據(jù)的傳輸比單信道可以更充分地利用頻譜資源以增強網(wǎng)絡的性能，完成多智能體間數(shù)據(jù)的并發(fā)傳輸，實現(xiàn)數(shù)據(jù)的分流處理、減少排隊等待時間和數(shù)據(jù)時延。然而，多信道必須處理好節(jié)點間的信道分配和協(xié)調(diào)，才能獲得比單信道更高的性能［3］。同時，時間同步是多個智能體間通信的重要組成部分，在并發(fā)傳輸機制中要求智能體之間有更為精準的時間同步，這樣在進行數(shù)據(jù)交換時才能具有統(tǒng)一的時間來實現(xiàn)智能體同步地接收到其他各個智能體發(fā)送的數(shù)據(jù)，以便智能體能夠?qū)崟r地進行數(shù)據(jù)融合，否則會造成功耗的增加和數(shù)據(jù)的丟失。

傳統(tǒng)的并發(fā)傳輸機制利用多信道技術來使用多個可用信道分擔數(shù)據(jù)負載，減少了通信過程中對信道的占用時間和避免了數(shù)據(jù)沖突，但沒有涉及如何提高時間同步的精準性，對于多信道引起的節(jié)點消失等問題難以高效解決，同時當智能體數(shù)量增加時，會造成數(shù)據(jù)的實時性差且節(jié)點功耗增加。進行多信道選擇的基礎首先是監(jiān)聽信道的狀態(tài)，因此本文首先采用馬爾可夫鏈對信道進行建模，并考慮信道的衰落特征，對通信網(wǎng)絡中信道好壞的變化情況進行精確地描述。并提出基于時間同步的并發(fā)傳輸機制，該機制利用一個參考節(jié)點廣播同步參考包，所有接收到這個參考包的節(jié)點都以本地時間記錄接收時間戳，之后通過交換時間戳完成所有接收到參考包的節(jié)點的同步［6］，同時利用多信道技術將網(wǎng)絡中的多個信道為多個節(jié)點所共用，當部分信道被占用時，節(jié)點能夠切換到其他空閑信道上，保證多個節(jié)點之間的通信同時進行，從而實現(xiàn)數(shù)據(jù)的同步并發(fā)傳輸。最后通過仿真實驗，驗證了該方法的有效性。

2 MAS中通信信道模型的建立

2.1 馬爾可夫鏈基本理論

馬爾可夫鏈是具有馬爾可夫性質(zhì)的離散時間隨機過程，在該過程中，在給定當前信息的情況下，過去對于預測將來是無關的［4］。馬爾可夫模型可應用于離散通信信道的建模與分析之中，考慮一個離散時間的隨機過程{Xn|n=0,1,2,…} ，該過程的取值范圍是非負整數(shù)，因此該過程中的狀態(tài)可以表示為i=0,1,…。無論什么時候，如果該過程處于狀態(tài)i，不考慮狀態(tài)i 之前的狀態(tài)，下一個狀態(tài)為狀態(tài) j 的概率 pij是一個大小固定的概率，則稱該過程為馬爾可夫鏈。即對所有的n ＞0,in-1,…,i0,i,j，有

2.2 一種離散時間馬爾可夫鏈信道模型

利用馬爾可夫鏈對信道進行建模時，信道的狀態(tài)模型用來描述不同的信道狀態(tài)，其中信道狀態(tài)之間的變化采用一組轉(zhuǎn)移概率來描述。將時間可分為多個相等長度時隙，時隙的長度記為T，信道可由一個離散狀態(tài)集合表示，在每一個時隙，信道處于某一狀態(tài)不改變，則一個離散通信信道的K狀態(tài)馬爾可夫模型的狀態(tài)集合為S={s0,s1,…,sK-1} 。K 個狀態(tài)用于區(qū)分信道狀態(tài)好壞的不同程度，如狀態(tài)s0為信道條件最好，狀態(tài)s1為信道條件次好，以此類推，狀態(tài)sK-1為信道條件最差。記第n 個時隙信道狀態(tài)為Sn，其中Sn?S 。令 pij為從狀態(tài)si轉(zhuǎn)移到狀態(tài)sj的轉(zhuǎn)移概率，則:

同時，考慮了瑞利衰落信道的特征。在瑞利衰落信道中，信噪比γ 是指數(shù)分布的概率密度函數(shù):

其中 γ0是平均信噪比。記{Γ1,Γ2,…,ΓK}為信噪比門限，并且按照升序進行排列，其中Γ1=0 且ΓK=+∞ 。

轉(zhuǎn)移概率 pi,i+1和 pi,i-1滿足:

其中，N(Γi)為水平通過率，pi為接收信噪比落入到區(qū)間[Γi,Γi+1)的概率。則信道的狀態(tài)轉(zhuǎn)移過程可由轉(zhuǎn)移矩陣Pc完全描述:

上述各式描述了離散時間馬爾可夫鏈信道模型，該模型不僅能夠很好地反映出用戶對信道占用的情況，而且考慮了信道的衰落特征，能夠精確地描述通信網(wǎng)絡中的信道好壞的變化情況，可以科學地預測將來時刻概率最大的空閑信道。

3 基于時間同步的并發(fā)傳輸機制

3.1 時間同步

在MAS 的通信過程中，智能體之間的信息傳遞需要同步進行，才能完成整個通信的實時性。利用時間同步的思想可實現(xiàn)智能體之間通信的實時性。該方法消除了發(fā)送的延遲對同步精度的影響，提高了時間同步的精準性。時間同步的具體過程如下:

Step1:參考節(jié)點周期性地廣播同步參考包。

Step2:節(jié)點i接收到第k個同步參數(shù)包，根據(jù)本地時鐘記錄的接收時刻為Tik，節(jié)點j 接收到第k 個同步參考包，根據(jù)本地時鐘記錄的接收時刻為Tjk。

Step3:持續(xù)接收參考節(jié)點廣播的同步參考包，并與鄰居節(jié)點交換信息，會得到m 個不同的差值。根據(jù)這些差值，計算出節(jié)點i與節(jié)點j之間的接收時間偏差:

Step4:在節(jié)點間時間同步后的一段時間，由于存在時鐘漂移，造成節(jié)點時間逐漸產(chǎn)生偏斜?？紤]時鐘偏斜時，使用最小二乘法線性擬合對時間戳進行處理，完成節(jié)點間時鐘偏差ΔT[i,j]的計算。

a0表示曲線擬合后的截距，即時鐘相位偏移；a1表示曲線擬合后的斜率，即時鐘偏斜。設曲線擬合后的橫坐標為x，縱坐標為 y，則

Step5:根據(jù)計算出的接收時間偏差和時鐘偏差，完成節(jié)點之間的同步。

3.2 并發(fā)傳輸機制

由于多信道傳輸比單信道傳輸在網(wǎng)絡性能上具有明顯的優(yōu)勢，因此在多信道上通過并發(fā)傳輸，可以有效地減小擁塞，實現(xiàn)負載均衡，提高網(wǎng)絡資源利用率；同時可以減少數(shù)據(jù)沖突，實現(xiàn)數(shù)據(jù)的分流，提高整個通信網(wǎng)絡的性能?；跁r間同步的并發(fā)傳輸機制示意圖如圖1所示。

圖1 基于時間同步的并發(fā)傳輸機制

并發(fā)傳輸機制的具體流程如下。

Step1:為每個節(jié)點生成信道選擇序列。利用偽隨機序列算法為每個節(jié)點生成不同的偽隨機序列作為信道選擇序列，并且每個節(jié)點采用各自的節(jié)點號作為偽隨機算法的種子。這里采用線性同余法來產(chǎn)生偽隨機序列，其計算公式為

其中a 為乘子，c 為增量，x0為種子，m 為模。

Step2:確定時間片選擇序列。首先將時間劃分為多個定長的時間片，由多個時間片組成一個超幀。利用偽隨機序列算法為每個節(jié)點生成不同的時間片選擇序列，節(jié)點按照生成的時間片選擇序列在每個超幀內(nèi)選擇一個時間片作為其蘇醒期。節(jié)點在每個蘇醒期偵聽信道狀態(tài)，并進行信息的收發(fā)。

Step3:節(jié)點定時向鄰居節(jié)點廣播自己的信道選擇序列和時間片選擇序列，這樣節(jié)點間就可以相互了解對方的信道選擇信息和蘇醒期、休眠期，以便于通信。

Step4:在初始時刻，所有節(jié)點都停留在各自信道選擇序列的第一個信道上。根據(jù)式（2）和式（4）計算信道的狀態(tài)轉(zhuǎn)移概率和信道衰落狀況，記為信道狀態(tài)集合S。當節(jié)點有信息需要發(fā)送時，節(jié)點通過信道狀態(tài)集合S 判斷信道的好壞。如果當前信道好，則直接在當前信道上通信，并執(zhí)行Step5；否則執(zhí)行Step6。

Step5:判斷發(fā)送節(jié)點和接收節(jié)點的蘇醒期是否處于同一時間片。當處于不同的時間片時，直接進行數(shù)據(jù)的發(fā)送；若蘇醒期恰好重合，則等待下一個超幀。這樣避免了節(jié)點消失的問題。

Step6:根據(jù)信道選擇序列確定所要切換的下一個信道，如果信道好，則發(fā)送節(jié)點與接收節(jié)點通過三次握手方式建立連接，并執(zhí)行Step5；否則繼續(xù)通過信道選擇序列搜索下一個信道，并判斷信道的好壞，直至找到合適的信道進行通信。

圖2 并發(fā)傳輸流程圖

Step7:參考節(jié)點周期性地廣播同步參考包，多個發(fā)送節(jié)點接收同步參考包，根據(jù)本地時鐘確定接收時間，通過式（6）和式（7）計算出接收時間偏差和時鐘偏差，完成節(jié)點之間的同步。

Step8:通信完畢后節(jié)點再切換到自己的默認信道上，從而完成整個信道選擇過程，實現(xiàn)基于時間同步的并發(fā)傳輸。

4 實驗分析

為了驗證本文所提出的方法的有效性，實驗采用了RoboCup-Rescue 仿真系統(tǒng)對其進行驗證。RoboCup-Rescue 是機器人救援仿真系統(tǒng)，包括中心智能體和移動智能體，中心智能體包括救護中心、消防中心和警察中心，移動智能體包括救護員、消防員和警察。實驗以救護智能體為例，說明本文所提方法對通信網(wǎng)絡性能的影響。實驗環(huán)境設定為:救護智能體數(shù)目為10（即網(wǎng)絡中的節(jié)點數(shù)為10），信道數(shù)目為13，仿真周期為300。

實驗一給出了信道在部分時隙下信道狀態(tài)的仿真結果。利用馬爾可夫鏈對信道狀態(tài)進行分析，信道狀態(tài)集合為S={0 ,...,10} ，圖3 中選取了其中2個信道在部分時隙下的信道狀態(tài)情況。

圖3 每個信道在不同時隙下的狀態(tài)

實驗二測試了傳統(tǒng)方法和本文方法對多智能體間通信網(wǎng)絡性能的影響，并利用平均時延這一性能指標對網(wǎng)絡性能進行衡量。

圖4 是采用傳統(tǒng)方法和采用本文方法對數(shù)據(jù)傳輸時延性能影響的比較。從圖中可以看出，采用本文方法可以降低平均時延。在初始時刻，即信道和網(wǎng)絡負載不是很重時，數(shù)據(jù)在多個信道上并發(fā)傳輸，平均時延較??；當發(fā)送數(shù)據(jù)越來越多時，信道和網(wǎng)絡負載過重，數(shù)據(jù)之間的排隊等待時間逐漸增大，因此平均時延也相對增加。但整體上來說采用本文方法降低了平均時延。

圖4 兩種方法的平均時延對比

實驗三測試了RoboCup-Rescue 仿真系統(tǒng)在300個仿真周期內(nèi)救護員救援市民人數(shù)的情況。

圖5 兩種方法下救援人數(shù)對比

圖5 顯示了采用傳統(tǒng)方法和采用本文方法后救護員救援人數(shù)的對比。從圖中可以看出，在采用本文方法之后，由于信息可以更加快速地發(fā)送給其他救護員，完成多個智能體間信息的快速共享，從而救護員能夠及時地救援市民，因此救援人數(shù)顯著提高。

5 結語

本文利用馬爾可夫鏈對信道進行建模，對通信網(wǎng)絡中信道好壞的變化情況進行精確的描述，科學地分析了信道在每一時刻的狀態(tài)情況。在傳統(tǒng)并發(fā)傳輸方法的基礎上提出了時間同步的思想，當智能體有數(shù)據(jù)需要發(fā)送時，監(jiān)聽信道狀態(tài)，如果信道忙則切換到其它空閑信道上進行傳輸，并利用時間同步的方法完成將多個數(shù)據(jù)同步地發(fā)送給一個智能體。最后通過仿真實驗驗證了本文方法的有效性。