藍牙散射網網間通信問題的研究

　　2003年11月推出的藍牙1.2版本提到的個人局域網也僅限于微微網（piconet）內的通信，在一個微微網中，即只有一個藍牙設備是主設備（Master），可以最多有7個從設備（Slave）。

　　這樣的網絡結構顯然無法滿足建立移動的個人局域網的需求。因此建立一個范圍更廣的散射網（Scatternet）是今后藍牙的發(fā)展趨勢。

　　散射網網間通信的問題

　　散射網是由多個微微網在時間和空間上相互重疊而構成的更加復雜的網絡拓撲結構。散射網中的藍牙設備既可以是某個微微網的從設備，也可以是另一個微微網的主設備。每個微微網的跳頻序列各自獨立，互不相關，同一微微網的所有設備跳頻序列同步，通過時分復用技術，一個藍牙設備便可以同時與幾個不同的微微網保持同步。由于散射網內的通信拓撲結構（通路和節(jié)點數的不同），微微網內（intra piconet）、網間(inter piconet)切換的順序，有效的數據流分配（即輪詢算法）等各種因素影響，藍牙利益集團（SIG）還沒有制定一個協(xié)議標準來規(guī)范散射網的建立和保證最小服務質量（Qos）的通信。

　　散射網通信問題的癥結

　　散射網通信面臨兩個急待解決的問題：

　　1.在復雜的網絡拓撲結構，如何使散射網內的兩個藍牙設備之間迅速建立通信路徑。

　　2.如何建立一種最佳的網間節(jié)點通信算法，從而減少因網間切換延遲造成的數據流傳輸效率的降低。

　　通過對國內外相關最新文獻的研究發(fā)現(xiàn)，在散射網網間通信問題的研究領域，這兩方面的問題往往是獨立研究的。也就是在散射網拓撲結構的研究中不能顧慮到網間節(jié)點快速通信及計算量的要求。而網間節(jié)點通信算法也提出了各種各樣的算法，但它們也基本不考慮實際的網絡拓撲結構。

　　為此本文提出了一種基于利用自定義路徑的散射網的隨機拓撲結構，并整合了網間自適應調度通信算法，從而提供了一種真正意義上的散射網內的無縫連接通信解決方案，為實現(xiàn)智能的個人局域網具有一定的借鑒意義。

　　自定義路徑的散射網拓撲結構

　　由于藍牙接入點在時間和放置地點不具有規(guī)律性，因此藍牙設備在散射網內的通信非常復雜。架構什么樣的散射網，以保證網間通信順暢成了研究的方向。國外對散射網組網提出過不同的理論，但都存在不同諸多問題。困擾的主要問題是路徑的選擇。目前主要可為分兩種路搜索模式，一種為地址表路徑搜索模式，另一種為需求搜索模式。這兩種方式要么需要通信節(jié)點具有龐大的記憶體，要么在網內發(fā)送廣播信息，會造成路徑確認延遲或網內泛濫的詢問路徑信息。為此，在這里提出一種基于藍牙設備地址的組網模式。它根據設備地址大小的不同，確認每個節(jié)點的網內通信范圍，當目的節(jié)點需要得到發(fā)送節(jié)點傳送的信息時，發(fā)送節(jié)點會判定目的節(jié)點是否在自己的通信范圍之內，如果沒有，則上傳信息給主節(jié)點，由主節(jié)點傳給相應的分節(jié)點(此分節(jié)點的通信范圍應涵蓋目的節(jié)點的MAC地址)，直到找到目的節(jié)點，這種方法稱為自定義路徑，它基本不會增加節(jié)點記憶體開銷，并且路徑方式是唯一確定的，同時這種散射網網的架構可以允許新的微微網或節(jié)點設備的加入。通過研究發(fā)現(xiàn)該組網方式結構清晰，定義明確,搜索路徑快捷。
網間自適應調度算法

　　在自定義路徑的散射網拓撲結構的基礎之上，為了提高網間通信的速率，需要建立網間切換的通信機制。研究發(fā)現(xiàn)，許多算法經常需要對藍牙協(xié)議做較大的改進和擴充后才能實現(xiàn)。而利用藍牙協(xié)議中的監(jiān)聽模式卻可以為微微網間的調度算法提供了一種靈活的方式，并且無須更改協(xié)議，這種方法稱為網間自適應調度算法，它是監(jiān)控各個鏈路上的流量并獲得流量變化的數據。

　　在分散網中,有些節(jié)點是多個微微網的成員,是不同微微網中的從節(jié)點或者主節(jié)點,這些節(jié)點稱為PMP(participant in multiple piconets)節(jié)點。它們采用時分復用方式分別參與到每個所連接的微微網中,數據才能在微微網間傳遞。

　　藍牙協(xié)議中的監(jiān)聽模式為微微網間調試算法提供了一個靈活的方式。如圖所示,從節(jié)點每間隔Tsniff處于監(jiān)聽狀態(tài),這時主從節(jié)點間可以傳輸數據,無論從節(jié)點收到屬于自己的數據包與否,監(jiān)聽狀態(tài)都維持Tsniffattempt個時隙。如果在監(jiān)聽狀態(tài)中收到傳給自己的數據包時，從節(jié)點還要繼續(xù)在下面的Tsnifftimeout個時隙和剩余的Tsniffattempt個時隙中較大的時隙里處于監(jiān)聽狀態(tài)，其它時間從節(jié)點可以處于休眠狀態(tài)，這時設備處于低能耗模式，設備間不能傳輸數據。Tsniff為監(jiān)聽周期，Tsniffattempt為監(jiān)聽時隙。

　　網間自適應調度算法是監(jiān)控各個鏈路上的流量并獲得流量變化數據。根據這些數據調整監(jiān)聽模式的關鍵參數，實時改變節(jié)點在各個鏈路上的監(jiān)聽時隙分配比例，反映鏈路上的流量變化，從而有效提高吞吐量，降低時間延遲。目前，藍牙協(xié)議中監(jiān)聽模式對微微網間調度的支持有些不方便和不明確的地方。處于監(jiān)聽模式后不能改變監(jiān)聽模式的參數。只有在退出監(jiān)聽模式后再進入監(jiān)聽模式才可能使新的參數生效。監(jiān)聽初始時隙由主節(jié)點決定，這使連接多個微微網的從節(jié)點上的多個鏈路的監(jiān)聽時隙可能嚴重相互重疊，使從節(jié)點不能很好地參與到其它的微微網中。因此對監(jiān)聽模式的操作方式需要作一些改進：進入監(jiān)聽模式以后，主節(jié)點或者從節(jié)點可以改變監(jiān)聽參數，不需要退出監(jiān)聽模式。主、從節(jié)點之間協(xié)商監(jiān)聽參數并在下一個時隙后開始使用新的監(jiān)聽參數。監(jiān)聽初始時隙由從節(jié)點決定，從節(jié)點根據所連接的微微網個數和監(jiān)聽參數使分配在各個鏈路上的監(jiān)聽時間最大限度地不發(fā)生重疊。

　　1. 數據流量變化的監(jiān)控

　　根據物理鏈路的數據流量，定義物理鏈路的繁忙程度B，簡稱為忙因子，取值范圍從0.0~1.0，值越大越繁忙。當PMP節(jié)點處于監(jiān)聽模式時，監(jiān)聽時隙和監(jiān)聽周期的比值應該接近于B值，因為能傳輸數據的監(jiān)聽時隙所占的比例應該與B成正比，B值越大，數據流量就越大，所需的監(jiān)聽時隙就應越長，反之亦然。則B與Tsniff和Tsniffattempt應該有關系：B∝Tsniffattempt/Tsniff 。已知B和Tsniff值，就可以計算出Tsniffattempt值。為了避免因為B值的變化而產生相應監(jiān)聽模式參數的不斷變化，只有當B值發(fā)生較大變化時，監(jiān)聽時隙和監(jiān)聽周期的值才作適當的放大或者縮小。

　　2. 最佳監(jiān)聽時隙分配計算

　　為實現(xiàn)分配在各微微網上的監(jiān)聽時間最大限度地不重疊，需要進行一些額外的簡單計算。假設某個節(jié)點連接N個微微網，它在每個微微網中都處于監(jiān)聽模式，監(jiān)聽模式的參數分別是Tisniffattempt和Tisniff，其中1≤i≤N。Tisniffattempt / Tisniff 為節(jié)點在第i個微微網中的監(jiān)聽時間比例，因此Tisniffattempt和Tisniff 參數必須滿足∑Tisniffattempt / Tisniff ≤1(1≤i≤N )。這時，如果節(jié)點取一個統(tǒng)一的監(jiān)聽間隔Tsniff，再將各個微微網的監(jiān)聽時隙分配到這個監(jiān)聽間隔中，使它們不重疊，實現(xiàn)監(jiān)聽時隙最大限度地不重疊。為了減少節(jié)點計算量，在實際應用中，假定Tisniff 不是連續(xù)取值，而是2的指數關系，即 Tisniff =2j(j＞1)。這時Tsniff 的取值為{ Tisniff }中的最大值。而Tisniffattempt 只需乘以某個2的倍數即可，使計算量大大降低了。

　　3. 監(jiān)聽參數計算

　　Lirx為在上個監(jiān)聽時隙里接受的數據個數，Litx為在上個監(jiān)聽時隙里發(fā)送的數據個數，流量為Fi。Fi=(Lirx+ Litx) Tisniff/( TmassniffTisniffattempt)，則Bi= Fi/Fmax。
PMP從節(jié)點連接了N個微微網，并是微微網P1到PN的從節(jié)點作為連接這些微微網的網橋，這時應在SB連接的微微網中都置于監(jiān)聽模式狀態(tài)。如果SB在微微網P1中，當主節(jié)點M1和SB之間的數據流量較小時，SB會被置于監(jiān)聽時隙較短的監(jiān)聽模式，若按照微微網中的主節(jié)點決定監(jiān)聽模式的參數，SB有充足的時間參與到其他的微微網中。但是當主節(jié)點與從節(jié)點SB之間的數據流量都較大時，SB會被主節(jié)點置于某種較忙的模式，這時監(jiān)聽模式參數之間就發(fā)生了沖突，因此需要SB決定和協(xié)調各個監(jiān)聽模式的參數。

　　假設SB計算出各個鏈路的忙因子Bi，1≤i≤N。Bi是各個鏈路的絕對值，若∑NBi ＞1，則首先需要對Bi作修整，得到相對值Binew，Binew=Bi /∑NBj。若∑NBi≤1，則Binew=Bi。根據Binew計算從節(jié)點監(jiān)聽模式參數Tisniffattempt和Tisniff，使它在不同微微網中的參與度與其忙因子成正比，并且參數滿足∑N Tisniffattempt/Tisniff≤1。若Tisniff確定并且等于Tsniff，則Tisniffattempt為Tisniffattempt=BinewTsniff。

　　若PMP主節(jié)點MS是微微網PS的主節(jié)點和微微網P1到PN的從節(jié)點。這時MS就不能將所有時間花在微微網PS中，它必須在某些時間切換到其他的微微網中。但是，MS是PS的主節(jié)點。它需要更多的時間處理PS中的事務，這將減少MS參與到P1到PN中的時間。因此必須根據微微網內和連接其他微微網的各個鏈路上的忙因子統(tǒng)一協(xié)調監(jiān)聽時間，但它們的計算方法基本相同。

　　只有當Bi發(fā)生較大變化時，對應的監(jiān)聽參數才會改變，以反映目前鏈路上的流量變化。當某個鏈路上有突發(fā)數據或者連續(xù)數據時，節(jié)點能有更多的時間比例參與到在這個鏈路上。或者當某個鏈路開始處于比較空閑的時候，節(jié)點能從這個鏈路上釋放出來參與到其他的鏈路上，使系統(tǒng)整體吞吐量較大，平均延遲較小。

　　假設δ為監(jiān)聽模式參數改變所需的閾值，Bihistory為Bi 的歷史平均值。這時，如果∣(Bihistory-Bi)/max(Bi，Bihistory )∣＞δ，說明Bi 開始有較大的變化，已經達到了參數可改變的界限。這時，如果Bi ＞Bihistory ，說明鏈路上的流量有較大增長，這時Ti’sniffattempt應增大，節(jié)點需要更多的監(jiān)聽時隙，允許主、從節(jié)點之間傳送更多的數據。相反，如果Bi ＜Bihistory，說明鏈路上的流量有較大減少，這時Ti’sniffattempt應減小，節(jié)點釋放出監(jiān)聽時隙，允許其他鏈路上有更多數據傳送。假設 Aisniff=∣(Bihistory-Bi)/max(Bi，Bihistory )∣，Ti’sniffattempt增大和減少的幅度與Aisniff有關，Aisniff越大，Ti’sniffattempt的增減幅度就越大。因此當Bi ＞Bihistory時，將Tisniffattempt更改為Tisniffattempt=(1+ Aisniff/2) Tisniffattempt。當Bi ＜Bihistory時，將Tisniffattempt更改為Tisniffattempt=(1- Aisniff/2) Tisniffattempt。
假設Tisniffattempt 和Tisniff都是有界定值的，即Tisniffattempt∈[Tminsniffattempt,Tmaxsniffattempt]，Tisniff∈[Tminsniff,Tmassniff]。因此，如果更改后的Tisniffattempt＜TminsniffattemptTisniff/ Tmassniff，則Tisniffattempt等于TminsniffattemptTisniff/ Tmassniff，但Tisniff應增大，即Tisniff=2Tisniff(2Tisniff＜Tmassniff)或者 (2Tisniff≥Tmassniff)。如果更改后的Tisniffattempt＞TmaxsniffattemptTisniff/ Tmassniff，則Tisniff應減小，即Tisniff=Tisniff/2(Tisniff/2＞Tminsniff)或者Tminsniff(Tisniff/2≤Tmassniff)。而Tisniffattempt=( Tmassniff+Tmaxsniffattempt) Tisniff/(2Tmassniff)。如果改變后Tisniffattempt/ Tisniff增大且造成∑NTisniffattempt/ Tisniff＞1，則Tisniffattempt和 Tisniff恢復原來的值。

　　假設節(jié)點連接的微微網個數為N，忙因子為Bi，歷史忙因子為Bihistory，忙因子變化率為Aiisniff，忙因子歷史值的權值為α，監(jiān)聽間隔為Tisniff，監(jiān)聽時隙為Tisniffattempt，可取的監(jiān)聽周期的最大值為Tmaxsniff，最小值為Tminsniff，可取的監(jiān)聽時隙的最大值為Tmaxsniffattempt，最小值為Tminsniffattempt，判斷改變監(jiān)聽參數的閾值為δ。調整Bihistory：Bihistory=αBihistory+(1-α) Bi.。

　　通過以上整個流程對監(jiān)聽參數的控制，完成了網間自適應算法。

　　結論

　　本文分析了影響藍牙散射網網間通信的主要問題，提出了基于自定義路徑的隨機拓撲結構下的網間通信模式，即網間自適應調度算法。它能夠排除各種散射網復雜的通信結構的影響，監(jiān)控各個鏈路上的流量，并獲得流量變化數據，根據這些數據調整監(jiān)聽模式的關鍵參數，實時改變節(jié)點在各個鏈路上的監(jiān)聽時隙分配比例，實現(xiàn)最佳監(jiān)聽時隙分配的方案。值得注意的是，散射網自定義路徑法與現(xiàn)有微微網的通信協(xié)議產生一定的沖突，因此建議在散射網通信模式下，加入對散射網規(guī)范協(xié)議的更改，如在散射網通信模式下取消主/從設備模式。另外對于網間通信，進入監(jiān)聽模式以后，主節(jié)點或者從節(jié)點可以改變監(jiān)聽參數，不需要退出監(jiān)聽模式，這也需要在散射網的通信協(xié)議中提出要求。綜上所述，網間自適應調度算法與自定義路徑拓撲結構的結合，為散射網內網間通信提供了一個理想的模型，值得深入研究。