藍(lán)牙散射網(wǎng)網(wǎng)間通信問題的研究

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

　　這樣的網(wǎng)絡(luò)結(jié)構(gòu)顯然無法滿足建立移動的個(gè)人局域網(wǎng)的需求。因此建立一個(gè)范圍更廣的散射網(wǎng)（Scatternet）是今后藍(lán)牙的發(fā)展趨勢。

　　散射網(wǎng)網(wǎng)間通信的問題

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

　　散射網(wǎng)通信問題的癥結(jié)

　　散射網(wǎng)通信面臨兩個(gè)急待解決的問題：

　　1.在復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如何使散射網(wǎng)內(nèi)的兩個(gè)藍(lán)牙設(shè)備之間迅速建立通信路徑。

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

　　通過對國內(nèi)外相關(guān)最新文獻(xiàn)的研究發(fā)現(xiàn)，在散射網(wǎng)網(wǎng)間通信問題的研究領(lǐng)域，這兩方面的問題往往是獨(dú)立研究的。也就是在散射網(wǎng)拓?fù)浣Y(jié)構(gòu)的研究中不能顧慮到網(wǎng)間節(jié)點(diǎn)快速通信及計(jì)算量的要求。而網(wǎng)間節(jié)點(diǎn)通信算法也提出了各種各樣的算法，但它們也基本不考慮實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

　　為此本文提出了一種基于利用自定義路徑的散射網(wǎng)的隨機(jī)拓?fù)浣Y(jié)構(gòu)，并整合了網(wǎng)間自適應(yīng)調(diào)度通信算法，從而提供了一種真正意義上的散射網(wǎng)內(nèi)的無縫連接通信解決方案，為實(shí)現(xiàn)智能的個(gè)人局域網(wǎng)具有一定的借鑒意義。

　　自定義路徑的散射網(wǎng)拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

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

　　根據(jù)物理鏈路的數(shù)據(jù)流量，定義物理鏈路的繁忙程度B，簡稱為忙因子，取值范圍從0.0~1.0，值越大越繁忙。當(dāng)PMP節(jié)點(diǎn)處于監(jiān)聽模式時(shí)，監(jiān)聽時(shí)隙和監(jiān)聽周期的比值應(yīng)該接近于B值，因?yàn)槟軅鬏敂?shù)據(jù)的監(jiān)聽時(shí)隙所占的比例應(yīng)該與B成正比，B值越大，數(shù)據(jù)流量就越大，所需的監(jiān)聽時(shí)隙就應(yīng)越長，反之亦然。則B與Tsniff和Tsniffattempt應(yīng)該有關(guān)系：B∝Tsniffattempt/Tsniff 。已知B和Tsniff值，就可以計(jì)算出Tsniffattempt值。為了避免因?yàn)锽值的變化而產(chǎn)生相應(yīng)監(jiān)聽模式參數(shù)的不斷變化，只有當(dāng)B值發(fā)生較大變化時(shí)，監(jiān)聽時(shí)隙和監(jiān)聽周期的值才作適當(dāng)?shù)姆糯蠡蛘呖s小。

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

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

　　3. 監(jiān)聽參數(shù)計(jì)算

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

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

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

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

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

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

　　通過以上整個(gè)流程對監(jiān)聽參數(shù)的控制，完成了網(wǎng)間自適應(yīng)算法。

　　結(jié)論

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