毛玲，李振波，陳佳品

(1. 上海電力學院 電氣工程學院， 上海 200090;2. 上海交通大學 電子與電氣工程學院，上海 200240)

0 引 言

對于多移動微機器人應用系統(tǒng)而言，機器人之間的通信是必要的,通常微機器人通信采用的是RF方式?？紤]到微機器人需實時地進行數(shù)據(jù)交換以便機器人之間合作快速完成任務，這意味著其個體之間的數(shù)據(jù)傳輸是有時間限制的，因此RF通信協(xié)議必須保證數(shù)據(jù)傳輸?shù)膶崟r性[1]。而且，因為移動微機器人RF網(wǎng)絡的特點，RF通信協(xié)議需支持節(jié)點的移動性及多跳通信能力。然而，目前典型的Ad-Hoc網(wǎng)絡協(xié)議重點放在解決最大吞吐量、最小時間延遲等問題上，而且大多數(shù)底層的商用網(wǎng)絡協(xié)議(如802.11、802.15.4等)因數(shù)據(jù)包沖突、隨機后退、錯誤包阻塞等問題而不能保證數(shù)據(jù)包在網(wǎng)絡中的實時傳輸。Lee等基于802.4的令牌環(huán)總線機制設計了WTRP協(xié)議[2]，當網(wǎng)絡中的某節(jié)點接收到了令牌，在一定時間內(nèi)它可以發(fā)送數(shù)據(jù)，并把令牌發(fā)送給它的前驅(qū)。然而，該協(xié)議不支持多跳通信，節(jié)點只能跟它的前驅(qū)或者后驅(qū)通信。Donatiello 和Furini[3]提出一個相似令牌傳遞機制，節(jié)點組成一個環(huán)，誰持有令牌誰有權(quán)發(fā)送數(shù)據(jù)，如果一定時間內(nèi)，發(fā)送失敗，就把令牌傳給下個節(jié)點，但是令牌只能朝著一個方向傳遞，需要網(wǎng)絡環(huán)一直保持連接，這限制了節(jié)點的移動性。Facchinetti[4]等用隱含的EDF機制保障了數(shù)據(jù)傳輸?shù)膶崟r性，然而該通信機制不支持多跳通信。802.15.4的無線通信方式保證了數(shù)據(jù)發(fā)送的安全性和多跳通信，但它允許任意推遲數(shù)據(jù)傳輸?shù)臅r間，故不能實現(xiàn)數(shù)據(jù)的實時通信。通過以上文獻調(diào)研可知，即使存在無線通信協(xié)議支持無線數(shù)據(jù)傳輸?shù)膶崟r性，但大多數(shù)不支持多跳通信。

本文在實時以太網(wǎng)協(xié)議(Real Time Ethernet Protocol,RT-EP)基礎上，設計了實時微機器人通信機制(Real Time Micro Robot Communication Protocol，RT-MRCP)，其使用令牌(消息優(yōu)先權(quán))傳送機制及時間槽通信機制來保證微機器人之間數(shù)據(jù)傳輸?shù)膶崟r性，該協(xié)議可以滿足多移動微機器人這種小規(guī)模無線網(wǎng)絡通信的應用場景，網(wǎng)絡中的節(jié)點數(shù)最多可達15個。

1 多微機器人的實時無線通信協(xié)議的設計

在設計的RT-MRCP協(xié)議中，每個節(jié)點都有一個發(fā)送消息隊列和一個接收消息隊列。消息隊列應用程序可將消息優(yōu)先級設置成0～127之間的任何值，其中127是最高優(yōu)先級。具有同一優(yōu)先級的消息根據(jù)先入先出(FIFO)規(guī)則放置在隊列中。當節(jié)點欲把消息發(fā)送給另一個節(jié)點時，把消息壓進發(fā)送隊列。RT-MRCP協(xié)議根據(jù)需要,處理從發(fā)送隊列中彈出的消息，并通過網(wǎng)絡把它發(fā)送到目的節(jié)點。接收節(jié)點把消息壓進接收消息隊列，根據(jù)應用所需彈出隊列中的消息。

為了描述網(wǎng)絡拓撲結(jié)構(gòu)，RT-MRCP定義了一個網(wǎng)絡連接圖。網(wǎng)絡連接圖中邊的值是兩個節(jié)點之間無線射頻信號質(zhì)量的函數(shù)，即兩節(jié)點間的鏈路質(zhì)量。其值表示成矩陣的格式即(Link Quality Matrix, LQM)，矩陣中的元素lqmij∈[0, max_lq]描述了節(jié)點Pi和Pj之間的鏈路質(zhì)量，其中max_lq為網(wǎng)絡中節(jié)點數(shù)，如圖1所示。LQM的每一列LQMk表示節(jié)點和它鄰居鏈路質(zhì)量。節(jié)點利用LQM選擇哪個節(jié)點傳輸令牌，并利用LQM決定源節(jié)點到目的節(jié)點的路徑。所有節(jié)點的lqmij都是LQM一個局部復制，當幀到達時，每個節(jié)點負責更新相應的列，并告知其他節(jié)點局部拓撲的改變。

圖1 網(wǎng)絡圖及相應的LQM及協(xié)議跳數(shù)的順序數(shù)

幀的結(jié)構(gòu)如圖2所示。所有類型的幀有同樣的幀頭，不同類型的幀其余部分不同。RT-MRCP幀描述成一系列指定的順序域，幀的傳輸按從左到右的順序，最先傳輸最左邊位。

圖2 幀的結(jié)構(gòu)

幀結(jié)構(gòu)具體分為：

1)header(幀頭)

(1)serial：幀的序列號域，2個字節(jié)的長度，用在錯誤恢復機制中。

(2)type：幀的類型域，1字節(jié)的長度分別定義了“token”、“authorization”和“message或drop”幾種類型的幀。

(3)src：源地址域，長度為1字節(jié)，指定了幀發(fā)起方的地址。

(4)dst：幀的目的地址域，長度為1字節(jié)，指定了幀接收方的地址。

事實上，RT-MRCP協(xié)議中，節(jié)點能夠被0～n-1地址識別，此地址稱為RT-MRCP地址。當節(jié)點欲發(fā)送數(shù)據(jù)時，填充src和dst域。因為無線信道共享，所有鄰居節(jié)點都會受到監(jiān)聽，但是僅有目的節(jié)點對其進行處理。

2)token(令牌幀)

(1)max_pri：最高優(yōu)先級數(shù)，長度為1字節(jié)，指定了MPM的優(yōu)先等級

(2)max_pri_id：最高優(yōu)先級數(shù)消息持有者的ID，長度為1字節(jié)，指定了MPM持有者的ID。

(3)age：年齡域，長度為2字節(jié)，用來找到具有同優(yōu)先級消息中最老的一個。

(4)lack：延遲確認域，長度為1字節(jié)，發(fā)送者的延遲確認域。

(5)nstat：節(jié)點的狀態(tài)域。是n個字節(jié)的數(shù)組，nstat[i]代表節(jié)點Pi的狀態(tài)為“reached”，“unreached“，“l(fā)ost”，“search”，即“到達”、“沒有到達”、“丟失”、“搜索”。

(6)LQM:鏈路質(zhì)量矩陣域，n2-n個字節(jié)，代表鏈路質(zhì)量矩陣。

3)authorization(授權(quán)幀)

authorization幀增加了aut_src域和aut_dst域。

(1)aut_src域：令牌持有者的源地址域，長度為1字節(jié)，指定了令牌持有者的源地址。

(2)aut_dst域：令牌持有者的目的地址域，長度為1字節(jié)，指定了令牌持有者的目的地址。

4)message(消息幀)

(1)priority域：消息幀優(yōu)先級數(shù)，長度為1字節(jié)，指定了消息的優(yōu)先級。

(2)msg_src域：消息源地址域，長度為1字節(jié)，指定了消息的源地址。

(3)msg_dst域：消息目的地址域，長度為1字節(jié)，指定了消息的目的地址。

(4)len:消息的長度域，長度為2字節(jié)，指定了消息的長度。

(5)data:幀的凈載荷域，幀凈載荷域的長度可變，長度為0-MTU字節(jié), MTU為幀凈載荷的最大長度。

通信協(xié)議RT-MRCP假設所有節(jié)點知道網(wǎng)絡拓撲(即所有的節(jié)點有同樣的LQM)且網(wǎng)絡是連通的，其包含的三個階段具體地如下所述：

(1)優(yōu)先權(quán)仲裁階段(Priority arbitration phase, PAP)：當一個節(jié)點Pk初始化了PAP，它創(chuàng)建了一個新的令牌幀，填充它的局部LQM到令牌幀的相關域，設nstat[i]為“unreached“?i∈[0,n-1]:i≠k。設置nstat[k]為“reached”。這就意味著在當前的PAP階段，令牌只到達了節(jié)點Pk還沒有到達其他的節(jié)點。節(jié)點Pk核對它發(fā)送隊列里具有最高優(yōu)先級消息的優(yōu)先級，然后用此優(yōu)先級的值和它的RT-MRCP地址分別設置max_pri和max_pri_id域。用消息age域的值設置令牌的age域(消息在隊列中等待的時間單位為milliseconds)。用這種方式節(jié)點Pk聲明它是MPM的持有者。節(jié)點Pk通過分析LQM，它知道哪個鄰居節(jié)點Pbl有最好的鏈路質(zhì)量并發(fā)送令牌給它。當節(jié)點Pbl收到此令牌，它設置nstat[bl]狀態(tài)為“reached”，然后用它局部的LQM更新令牌的LQM域，并保存它。然后它查找令牌的max_pri域并與它發(fā)送消息隊列的最高優(yōu)先級比較，如果它有更高的優(yōu)先級消息，則調(diào)整max_pri和max_pri_id域。如果優(yōu)先級相同，它核對age域，如果持有的消息更老，它更新此令牌。然后，它選擇一個具有最好鏈路質(zhì)量且令牌沒有到達的節(jié)點，發(fā)送令牌給此節(jié)點。如果它只監(jiān)聽到了前驅(qū)(發(fā)送令牌給它的節(jié)點)，它歸還令牌給它的前驅(qū)。這意味著在同一個PAP階段，節(jié)點可能接收到令牌數(shù)次。這個過程一直被重復直到令牌到達過所有節(jié)點即nstat[i]=reached?i。令牌到達的最后一個節(jié)點，其知道誰是MPM的持有者，并且負責發(fā)送“authorization(授權(quán))”給MPM持有者。

(3)消息傳遞階段(Message transmission phase, MTP)：當MPM的持有者接收到了“authorization”消息后，從消息隊列中取出最高優(yōu)先級的消息并創(chuàng)建“message”消息，設置data域并填充msg_src和msg_dst，然后發(fā)送消息給這路徑的第一個節(jié)點。當?shù)谝粋€節(jié)點接收到這個消息，它核對msg_dst域，如果是自己則停止MTP，并開始ATP。否則，它把消息發(fā)送給路徑中它的下一個節(jié)點，重復這個過程，直到消息到達目的節(jié)點。如果消息到達了目的節(jié)點，在初始化PAP之前，目的節(jié)點用它的RT-MRCP地址填充新令牌的lack域，此令牌能夠到達前面消息的發(fā)送者，它能夠通過查找lack域知道消息是否發(fā)送成功。

每個機器人節(jié)點通過傳送封裝局部LQM的幀了解頻繁變動的RF網(wǎng)絡拓撲結(jié)構(gòu)。每個節(jié)點通過填充其LQM矩陣的相應列，從而可容易獲得實時的RF網(wǎng)絡拓撲信息。事實上，當節(jié)點發(fā)送數(shù)據(jù)幀時，由于采用無線廣播的方式，它的鄰居節(jié)點都能夠監(jiān)聽到，每個節(jié)點收到后，自動更新其自己LQM，然后將其轉(zhuǎn)發(fā)給其他鄰居節(jié)點。因為LQM被頻繁地傳輸?shù)矫總€節(jié)點，故節(jié)點都能及時地更新網(wǎng)絡的拓撲信息。

2 通信協(xié)議的協(xié)議的實時特性

RT-MRCP協(xié)議之所以能夠保證數(shù)據(jù)傳輸?shù)膶崟r性，因為協(xié)議的每一階段持續(xù)的時間有界且已知。如果網(wǎng)絡是連通的，保持網(wǎng)絡圖連通的最少的邊數(shù)為n-1，其中n為圖中頂點數(shù)，所以在PAP階段最糟糕的情況應該是2n-3跳，如圖3所示。此外，如果發(fā)生錯誤例如節(jié)點失敗、節(jié)點重新插入或者丟失，此階段有同樣的持續(xù)時間，因為傳輸失敗的令牌所花費的時間與需要發(fā)送和返回一個令牌所花費的時間一致。例如，假設節(jié)點Pk是節(jié)點Pa僅有的鄰居，如果協(xié)議正常運作，節(jié)點Pk發(fā)送令牌給節(jié)點Pa，為了繼續(xù)PAP，節(jié)點Pa返回令牌給Pk，節(jié)點Pk繼續(xù)PAP。如果節(jié)點Pa發(fā)送令牌以后，出現(xiàn)異常，節(jié)點Pk將等待一段時間(timeout)，傳遞令牌給另一個節(jié)點，繼續(xù)PAP。實際上，上述兩種情況所花費的時間相同，因為節(jié)點Pa需要返回令牌的時間與Pk等待的時間(timeout)相等。

圖3 PAP階段最糟糕的情況

在ATP和MTP階段，路徑由Dijkstra’s Algorithm決定[5]。根據(jù)此算法，如果網(wǎng)絡連通，從源節(jié)點到目的節(jié)點最大的跳數(shù)是n-1，n是圖中總頂點數(shù)。因此每個階段都有一個有界的持續(xù)時間。然后在節(jié)點失敗或者丟失的情況下，為了不妨礙網(wǎng)絡的正常運行節(jié)點將舍棄authorization和message的發(fā)送。例如，假設節(jié)點Pk計算一條到目的節(jié)點Pd由n-1個節(jié)點組成的路徑，如果沿著此路徑的第一跳就失敗了，例如Pk傳遞給了Pb，Pb失敗或者丟失，Pk將尋找另一條到Pd路徑。但是，路徑總的跳數(shù)可能大于允許的最大跳數(shù)n-1，所以為了不妨礙網(wǎng)絡的正常運行，節(jié)點將舍棄傳遞authorization和message消息。

圖4 RT-MRCP協(xié)議每個階段的跳數(shù)

通信協(xié)議RT-MRCP的連續(xù)地重復著每一階段，如圖4所示。最糟糕的情況下，PAP持續(xù)時間為tpa= (2n-3)tt，ATP持續(xù)時間為tat= (n-1)ta，MTP持續(xù)時間為tmt= (n-1)tm。tt是token消息傳遞的最大持續(xù)時間，ta是authorization消息傳遞的最大持續(xù)時間，tm是message消息傳遞的最大持續(xù)時間。tt、ta、tm值取決于協(xié)議的參數(shù)例如節(jié)點數(shù)量、數(shù)據(jù)速率、最大發(fā)送單元的長度和802.15.4協(xié)議。802.15.4的操作細節(jié)不是本文討論的重點。無論怎樣，802.15.4幀的發(fā)送速率是250 kbps。一個節(jié)點在發(fā)送之前總是等一段時間，大概是120 μs。與網(wǎng)絡速率無關，802.15.4幀的一部分(preadble and header)總是要以250 kbps的速度發(fā)送大概是986 μs。幀發(fā)送的持續(xù)時間如下：

(1)

L是擴展的802.15.4幀的負載包括整個幀頭(令牌幀L=11+n2，authorization幀:L=8,message幀：L=11+MTU)，tx_rate為幀的發(fā)送速率，在最糟糕的情況下，令牌消息到達每個節(jié)點的間隔為：ttoken= 2ta+tat+tmt。具有最高優(yōu)先權(quán)的消息在最糟糕的情況下，遭受的延遲為twc=2(tpa+tat+tmt)。

3 試驗

為了驗證通信協(xié)議RT-MRCP的性能，試驗中用四個裝備 IEEE802.15.4設備的微機器人做了如下試驗[6]。

圖5 協(xié)議的優(yōu)先級行為

第一個試驗的目的是驗證RT-MRCP協(xié)議基于優(yōu)先級的消息交換機制。在由四個節(jié)點組成的網(wǎng)絡中，所有的節(jié)點都產(chǎn)生飽和交通的情形。每個節(jié)點都有一個包含20條消息的發(fā)送消息隊列。發(fā)送消息隊列應用程序可將消息的消息優(yōu)先級設置成1～20之間的任何值，目標是測量不同優(yōu)先級消息遭受的延遲，結(jié)果如圖5所示。從圖5可知，消息的優(yōu)先級越高所遭受的的消息延遲越少，換句話說消息延遲與消息優(yōu)先級成反比。

第二個試驗目的是驗證通信協(xié)議RT-MRCP端到端的吞吐率。做了兩種情況下的試驗，一種是在最好的情況下，另一種是在最糟糕的情況下。在最好的情況下，分別創(chuàng)建兩個、三個和四個節(jié)點完全連通的網(wǎng)絡。在PAP階段，總是持續(xù)n-1跳，ATP階段和MTP都是一跳。為了確定有效的瞬時帶寬，某一節(jié)點以一定的速率發(fā)送新令牌消息，如果能夠收到隱含確認消息，那么就將發(fā)送速率提高重新進行測試，直至得出最終的結(jié)果。測量的結(jié)果如表1所示。

表1 端到端帶寬的實驗測量結(jié)果 kbps

在最糟糕的情況下，分別創(chuàng)建兩個、三個和四個節(jié)點完全連通的網(wǎng)絡。在PAP階段，總是持續(xù)2n-3跳，ATP階段和MTP都是n-1跳。為了確定有效的瞬時帶寬，正如最好的情況所采用的方法，某一節(jié)點以一定的速率發(fā)送新令牌消息，如果能夠收到隱含確認消息，那么就將發(fā)送速率提高重新進行測試，直至得出最終的結(jié)果。理論上網(wǎng)絡節(jié)點越多字節(jié)數(shù)越大帶寬應該越小，但從表1可以看出，實測結(jié)果和理論上的不同，節(jié)點越多字節(jié)數(shù)越大帶寬越大，這是因為協(xié)議程序執(zhí)行時間比較少，瓶頸由額外的UDP/IP層組成。事實上，根據(jù)試驗的測量數(shù)據(jù)可知，從產(chǎn)生通信中斷到應用層接收到數(shù)據(jù)的延時大概有0.5 ms～1.5 ms，此延時對較小的數(shù)據(jù)包影響比較大，對較大的數(shù)據(jù)包影響比較小。

4 結(jié)束語

本文使用令牌傳送機制及時間槽通信機制設計了通信協(xié)議RT-MRCP，其滿足了數(shù)據(jù)傳輸?shù)膶崟r性，可以運行在802.15.4基礎之上。所設計的RT-MRCP協(xié)議通過共享節(jié)點間的鏈路質(zhì)量矩陣來了解頻繁變動的網(wǎng)絡拓撲結(jié)構(gòu)。并設計了實時通信RT-MRCP協(xié)議的錯誤處理機制，分析了通信RT-MRCP協(xié)議的實時特性，試驗證明了通信協(xié)議RT-MRCP能滿足檢測系統(tǒng)對微機器人通信協(xié)議實時性的要求即最大消息傳輸時延小于1 s。所設計的RT-MRCP協(xié)議比較適合小規(guī)模網(wǎng)絡的應用，雖然允許的網(wǎng)絡中最大節(jié)點數(shù)只有15，但是這足以滿足多移動微機器人系統(tǒng)應用的需求。