ＢＧＮ：一種新的藍牙傳感器網(wǎng)絡(luò)分散網(wǎng)構(gòu)造算法

（華南理工大學 計算機科學與工程學院， 廣州 510641）

摘 要：在藍牙分散網(wǎng)中，橋節(jié)點的數(shù)量和每個橋節(jié)點的度是影響主干網(wǎng)性能的重要因素。在生長樹的基礎(chǔ)上提出一種新的藍牙分散網(wǎng)構(gòu)造算法——BGN。該算法利用生長樹主干節(jié)點間預(yù)留的連接將樹改造成網(wǎng)，所形成的分散網(wǎng)能夠在保持一定程度連通性的同時避免過多的冗余鏈接。仿真實驗的結(jié)果表明，該算法所生成的分散網(wǎng)結(jié)構(gòu)在橋節(jié)點數(shù)量、平均路徑長度、網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)最大傳輸流量方面具有優(yōu)勢。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；藍牙；分散網(wǎng)

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)01030204

BGN：novel scattenet formation algorithm for bluetoothbased sensor networks

XIE Rong，QI Deyu， LI Yongjun

(School of Computer Science Engineering， South China University of Technology， Guangzhou 510641， China)

Abstract:In a bluetooth scatternet， the number of bridges and the degree of each bridge are significant factors that determine the performance of the backbone.This paper proposed a new bluetooth scatternet formation algorithm (BGN)， which was derived from the tree structure by adding reserve links among its branch nodes. The resulting scatternets maintain a degree of connectivity while avoiding too many redundant links. Simulation results show that the proposed protocol has prominent predominance on aspects of the number of bridge nodes， average shortestpath length， reliability of networks and maximum trafficflows.

Key words:wireless sensor network; bluetooth; scatternet

藍牙是一種先進的近距離無線通信技術(shù)，工作在24 GHz的ISM頻段，具有低成本、低功耗、抗干擾性能好和組網(wǎng)方便等突出優(yōu)點，日益成為無線傳感器網(wǎng)絡(luò)的首選通信方式。當網(wǎng)絡(luò)中節(jié)點較多時，需要一種高效的拓撲構(gòu)造算法將這些節(jié)點組成多個皮網(wǎng)，再通過橋節(jié)點將皮網(wǎng)連接以形成一個藍牙分散網(wǎng)。

在藍牙無線傳感器網(wǎng)絡(luò)中，橋節(jié)點的數(shù)量和每一個橋節(jié)點的度在很大程度上決定了網(wǎng)絡(luò)的性能和生存時間。橋節(jié)點數(shù)越多，網(wǎng)絡(luò)的可靠性越高，平均傳輸路徑越短。但由于橋節(jié)點是活躍節(jié)點，其無線模塊必須隨時處于監(jiān)聽狀態(tài)，而文獻[1]指出，無線模塊收發(fā)數(shù)據(jù)需要消耗很多能量，即使處于監(jiān)聽狀態(tài)，其消耗的能量也與接收一條信息所消耗的能量大致相當。因此，橋節(jié)點數(shù)量增加會降低網(wǎng)絡(luò)的整體生存時間。如何在不影響網(wǎng)絡(luò)的可靠性和連通性的情況下控制橋節(jié)點的數(shù)量和度是藍牙分散網(wǎng)形成算法研究中的核心問題之一。

1 研究現(xiàn)狀

近年來，國內(nèi)外學者從不同角度對藍牙分散網(wǎng)構(gòu)造問題進行了廣泛和深入研究，這些拓撲結(jié)構(gòu)大致劃分為網(wǎng)狀和樹狀。

Zaruba等人[2]提出一種樹型拓撲結(jié)構(gòu)組網(wǎng)算法(BlueTree)，該算法充分利用樹型結(jié)構(gòu)的特點(N個設(shè)備僅需N-1條通信鏈接即可互連在一起)較好解決了冗余通信鏈接過多的問題，但是這種樹型結(jié)構(gòu)的可靠性很差，橋節(jié)點極易成為通信中的瓶頸。Wang等人[3]提出一種網(wǎng)狀拓撲結(jié)構(gòu)的組網(wǎng)算法(BlueNet)，其目的是構(gòu)造一個平滑的網(wǎng)絡(luò)結(jié)構(gòu)以提高網(wǎng)絡(luò)的可靠性，但由于沒有對皮網(wǎng)數(shù)目和冗余通信鏈接進行控制，所形成的自組織網(wǎng)內(nèi)常常因過多皮網(wǎng)之間的干擾使得通信性能較低。Saginbekov等人[4]提出了一種基于最短路徑樹的分散網(wǎng)構(gòu)建算法，試圖通過最小化每一輪的通信消耗達到節(jié)能的目的，但該算法屬于集中式算法，不適用于無線傳感器網(wǎng)絡(luò)這種分布式環(huán)境。Song等人[5]提出了dBBlue算法，引入de Bruijn圖來構(gòu)建藍牙分散網(wǎng)的路由主干，改善路由的性能，它所形成的網(wǎng)絡(luò)通信直徑最多只需O(log n)跳，而網(wǎng)絡(luò)出現(xiàn)沖突的概率只有O(logn/n)。Chang等人在文獻[6]中提出了一種relayreduction算法來減少橋節(jié)點的數(shù)量和減少路由跳數(shù)，但該算法時間復(fù)雜性較高。文獻[7]則提出一種鏈形結(jié)構(gòu)的分散網(wǎng)構(gòu)造算法，該算法具有創(chuàng)建時間短和拓撲結(jié)構(gòu)容易動態(tài)維護等特點，但這種結(jié)構(gòu)只適用于節(jié)點是線性布置的網(wǎng)絡(luò)。

以上介紹的幾種經(jīng)典藍牙分散網(wǎng)拓撲構(gòu)成算法或多或少存在著橋節(jié)點數(shù)目較多、平均傳輸路徑較長、可靠性差、某些節(jié)點負荷過重和網(wǎng)絡(luò)拓撲動態(tài)維護性能差等缺點。本文提出了一種新穎的網(wǎng)狀結(jié)構(gòu)的藍牙分散網(wǎng)拓撲構(gòu)成算法，即BGN，并通過仿真對其性能作了分析。與以往算法相比，該算法實現(xiàn)簡單，在橋節(jié)點數(shù)量、可靠性、平均路徑長度、網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)最大傳輸流量方面有顯著優(yōu)勢。

2 BGN算法 

21 定義

定義1 皮網(wǎng)(piconet)。一個皮網(wǎng)由一個主節(jié)點和至多七個從節(jié)點組成，即

Pi={(Mi，Si， j)|1≤j≤7}

其中：Mi是皮網(wǎng)Pi的主節(jié)點，Si， j是由Mi所支配的從節(jié)點。

定義2 分散網(wǎng)(scatternet)。當兩個或兩個以上獨立、非同步的皮網(wǎng)在時間和空間上部分重疊時就形成了散射網(wǎng)。

S={∪Pi|i≥2，PipathPj}

其中：PipathPj表示存在一條從皮網(wǎng)Pi到Pj的路徑。

定義3 橋節(jié)點(bridge)。該節(jié)點在多個皮網(wǎng)中分時工作，從一個皮網(wǎng)中接收數(shù)據(jù)再轉(zhuǎn)發(fā)到另一個皮網(wǎng)。橋節(jié)點可以是一個皮網(wǎng)中的主設(shè)備同時是其他皮網(wǎng)中的從設(shè)備（主/從橋）或在各皮網(wǎng)中均是從設(shè)備(從/從橋)。

B={tk|tk∈Pi∩Pj}

如圖1所示，皮網(wǎng)P1、P2和P3在時空上部分重疊，構(gòu)成一個藍牙分散網(wǎng)。其中：M2是皮網(wǎng)P2的主節(jié)點，M2控制著從節(jié)點S1和橋節(jié)點B21和B23。

定義4 生長樹。從種子點出發(fā)尋找鄰節(jié)點，將它們作為種子節(jié)點的兒子節(jié)點。鄰節(jié)點成為兒子節(jié)點后將變成種子點，所有的種子點以平等機會尋找鄰近點，直到其周圍沒有空白節(jié)點。該過程就像樹不斷地分叉生長一樣，故稱為生長樹。

圖2實線所構(gòu)成的拓撲結(jié)構(gòu)就是一個生長樹型藍牙分散網(wǎng)實例。其中，葉子節(jié)點為從節(jié)點，樹干節(jié)點除了擔任主節(jié)點角色，還擔任橋節(jié)點角色。

22 基本思路

221 藍牙生長網(wǎng)

觀察圖2的生長樹可以看到，生長樹只使用了網(wǎng)絡(luò)所有無線鏈路的一部分，除此之外，在樹干節(jié)點間還存在著一定數(shù)量的冗余邊（虛線表示）。加入這些邊后，樹型拓撲結(jié)構(gòu)變?yōu)榫W(wǎng)狀結(jié)構(gòu)，主干節(jié)點的數(shù)量卻保持不變，而網(wǎng)絡(luò)在可靠性和吞吐率等方面比原先的樹型結(jié)構(gòu)有了顯著提高。由于這種結(jié)構(gòu)是在生長樹的基礎(chǔ)上構(gòu)建，稱這種結(jié)構(gòu)為藍牙生長網(wǎng)（bluetooth grown net），稱主干節(jié)點加入的邊為候選邊(candidate edge)。

定義5 藍牙生長網(wǎng)。給定圖G(V，E)和其生長樹T(V′，E′)，V′V，E′E，M是G′的樹干節(jié)點集合，|u|表示節(jié)點u的從節(jié)點數(shù)量，則

BGN={T∪e(u，v)|e(u，v)∈E，u∈M，v∈M，|u|≤7，|v|≤7}

定義6 候選邊。給定生長樹T，主干節(jié)點u的候選邊集為

ceu={eu，v||eu，v|≤R，u∈M，v∈M}

其中：R是節(jié)點的通信半徑，M是樹干節(jié)點的集合。

222 位置預(yù)留

根據(jù)定義6，兩個樹干節(jié)點只要它們的距離小于等于R，就存在候選邊，但該候選邊能不能加入到生長樹還要看這兩個樹干節(jié)點有沒有“滿”。只要其中一個樹干節(jié)點是“滿”的，就不能添加候選邊。這種情況容易在節(jié)點密度較大時出現(xiàn)(如3.1節(jié)所示)，影響整個網(wǎng)絡(luò)可添加的候選邊數(shù)。

為了避免這種情況，本文采用位置預(yù)留的方法，即在構(gòu)建生長樹結(jié)構(gòu)時，每個樹干節(jié)點預(yù)先保留θ（0≤θ<7）個位置用于將來添加候選邊。θ的取值影響生長樹主干節(jié)點和葉子節(jié)點的數(shù)量。θ取值越少，網(wǎng)絡(luò)可添加的候選邊越少，可靠性就越低；θ的取值越大，可添加的候選邊越多，但橋節(jié)點的數(shù)量也隨著增加，影響網(wǎng)絡(luò)的生存時間。根據(jù)第3章的仿真實驗結(jié)果，θ=2或1時，網(wǎng)絡(luò)的性能最佳。

23 BGN構(gòu)造算法

藍牙生長網(wǎng)由兩個階段構(gòu)成：a)構(gòu)建牙生長樹，具體過程可參見文獻[8]；b)各樹干節(jié)點分別運行BGN算法，通過競爭的方法[9]加入候選邊。樹干節(jié)點i的競爭優(yōu)先權(quán)Pi為

Pi=(1+|Bi|)/2T(1)

其中:T是競爭時間周期長度，|Bi|是節(jié)點i的橋節(jié)點數(shù)量。Pi在算法中用延遲時間來表示，Pi越大，則需延遲等待的時間越長，而Pi的大小取決于節(jié)點i的橋節(jié)點數(shù)量，橋節(jié)點越多，延遲時間越長。這樣是為了讓出口少的皮網(wǎng)優(yōu)先構(gòu)建冗余鏈路，提高網(wǎng)絡(luò)的可靠性。

procedure for all nodes during timeTQ

s1 if number of slave≥7 then exit;

s2 t←(1+si)/2T

s3 schedule a delay in t second

s4 if receive any query(ALL，sender) msg in t second then

cancel the scheduler

parent←sender

role←loser

else

broadcast query(ALL，myaddr) msg

role←winner;

s5 wait until TJ period arrive

procedure for nodes where role=winner during time TJ

s1 if receive join(parent， sender) msg sender not in Bi

add a link to the sender

Bi←Bi∪ sender

send accept(sender，myaddr) msg 

s2 if receive none of join msg then 

exit

else

wait until next TQ period arrive

procedure for nodes where role=loser during time TJ

s1 t←rand(0，Tj/2)

s2 delay t second

s3 send join(parent，myaddr) msg 

s4 if receive accept msg from parent then

add a link to parent

Bi←Bi∪ sender

s5 wait until next TQ period arrive

BGN是一種競爭算法，它將競爭周期T均勻劃分為兩等份，即Tq和Tj。各主干節(jié)點在Tq周期競爭發(fā)送query消息和在Tj周期競爭發(fā)送join消息。

當Tq周期到來時，各樹干節(jié)點根據(jù)式（1）計算各自的延遲時間t。如果在t s內(nèi)，節(jié)點沒有收到周圍節(jié)點發(fā)送的query消息，則競爭成功，向周圍節(jié)點廣播query消息；收到query消息的節(jié)點成為失敗者，不再廣播query消息。

當Tj周期到來時，失敗者隨機延遲相應(yīng)時間后向勝利者發(fā)送join消息，勝利者將第一個向它發(fā)送join消息且不是它的從節(jié)點的節(jié)點加入皮網(wǎng)，并向它發(fā)送accept消息，對其余申請不予理睬；收到accept消息的節(jié)點也將接收節(jié)點加入皮網(wǎng)，從而構(gòu)建出一條鏈接。以上過程如此反復(fù)，直到節(jié)點“滿”或周圍沒有節(jié)點發(fā)送join消息，算法結(jié)束。

圖3給出了一個候選邊添加實例。圖中的節(jié)點均為主干節(jié)點，實線是已建立的連接，虛線為候選邊。在Tq周期，各主干節(jié)點根據(jù)式（1）計算自己的時延，其中，節(jié)點a延時最短，d、f、g次之，b、c、e最長，但只有節(jié)點a、d、f、g競爭成功。它們向周圍廣播query消息，其余節(jié)點在收到消息后，不再向外發(fā)送消息。在Tj周期，收到query消息的節(jié)點先判斷自己是否已經(jīng)與源節(jié)點創(chuàng)建了連接，如果沒有，則向源節(jié)點發(fā)送join消息，通過本輪競爭，候選邊de和fg被加入網(wǎng)絡(luò)。

3 仿真分析

本章用仿真分析的方法對BGN算法進行性能評估，主要評估候選邊數(shù)、主干節(jié)點數(shù)目、路徑長度、網(wǎng)絡(luò)可靠性和吞吐率等。仿真工具為NS2[10]。

31 θ取值對候選邊和主干節(jié)點的影響?yīng)?/p>

本組實驗主要評估本文2.2.2節(jié)位置預(yù)留參數(shù)θ的取值對算法性能的影響，并找出最佳的θ取值。實驗環(huán)境如下：N個節(jié)點隨機分布在100×100的場景中，N從50變化到250，步長為5，每個節(jié)點的通信半徑R均為40 m，對于每一個場景，重復(fù)實驗100次，實驗結(jié)果取平均值。

圖4是θ在取不同值情況下藍牙生長樹的皮網(wǎng)平均從節(jié)點數(shù)量。可以看到，平均從節(jié)點數(shù)隨著節(jié)點密度的增大而增加，但平均從節(jié)點數(shù)均未超過5.5個。這說明網(wǎng)絡(luò)中絕大多數(shù)主干節(jié)點仍有空閑位置，這些空閑位置可以用來添加候選邊。θ的取值越大，預(yù)留給候選邊的位置越多。但并不是θ越大越好，還需要看主干節(jié)點總數(shù)和可添加的候選邊數(shù)。

圖5是θ在取不同值情況下BGN算法在生長樹上添加的候選邊數(shù)。可以看到，在節(jié)點密度較低（N≤120）的情況下，除θ=3外，其余三條曲線都很接近，添加到生長樹上的候選邊數(shù)大致相當。但隨著節(jié)點密度的增加，算法的性能逐漸拉開，當N=250，θ=3可添加112條候選邊，θ=2只能添加60.3條候選邊，而θ=1只能添加37.6條邊。可見在節(jié)點密度較大的情況下，θ取值對候選邊數(shù)的影響非常大。在四條曲線中，只有θ=0添加的候選邊最少，大約只有10.3條，且沒有隨著節(jié)點數(shù)的增加而增加。這是因為在生長樹上添加候選邊，候選邊兩端的節(jié)點都必須有空閑位置，在節(jié)點密度較大的情況下時，主干節(jié)點容易由于“滿”而無法添加候選邊。

圖6是BGN、BlueNet和BlueTree算法在各種節(jié)點密度情況下構(gòu)建藍牙分散網(wǎng)所需的主干節(jié)點數(shù)。可以看到，BlueTree的主干節(jié)點最少，BlueNet最多，BGN的主干節(jié)點數(shù)稍大于BlueTree，其主干節(jié)點數(shù)隨著θ的增加而增加。以200個節(jié)點為例，BlueTree主干節(jié)點數(shù)為39.8個，根據(jù)圖論，BlueTree的主干節(jié)點間共有38.8條邊；而BGN在θ=1和2時主干節(jié)點為42.4和48.9個，比BlueTree多3.6和9.1個，分別增加了904%和22.8%，但其主干節(jié)點間增加了19.1和40.2條邊，分別增加了49.2%和103.6%。與BlueTree算法相比，在同一網(wǎng)絡(luò)構(gòu)建骨干網(wǎng)，BGN算法的骨干網(wǎng)節(jié)點數(shù)要稍大于BlueTree，但其骨干網(wǎng)的鏈路數(shù)比BlueTree有了顯著的增加，骨干網(wǎng)的吞吐率和可靠性大大提高。綜合圖5和6，BGN算法的θ取1或2時，算法的性能最優(yōu)。

32 平均路徑長度

平均路徑長度是指藍牙網(wǎng)絡(luò)中任意節(jié)點到基站的最短路徑長度（跳數(shù)）平均值，其計算式為ASP=ni=1min_hop(i，0)/n。平均路徑長度主要影響數(shù)據(jù)傳輸?shù)哪芎暮蜁r延，這是因為跳數(shù)越少，意味著轉(zhuǎn)發(fā)的次數(shù)越少，消耗的通信能量越少，爭用共享信道的等待時間也隨著減少了。任意給定一個連通的網(wǎng)絡(luò)，可以求出其最小平均路徑長度，記為ASPmin。

圖7是BGN、BlueNet和BlueTree算法所生成分散網(wǎng)在各種節(jié)點密度情況下的平均路徑長度。可以看出，這幾種算法的平均路徑長度隨著節(jié)點密度的增加而減少，當網(wǎng)絡(luò)節(jié)點數(shù)≥120個后，平均路徑長度基本保持不變，且所有算法的平均路徑長度均大于ASPmin，這是因為所構(gòu)建的藍牙分散網(wǎng)只用了網(wǎng)絡(luò)的一部分連接。在這幾種算法中，BlueTree算法的平均路徑長度最短，BGN算法的性能與BlueTree接近，而BlueNet的平均路徑長度最長，這是因為BGN算法和BlueTree算法都是直接在兩個主節(jié)點間構(gòu)建通路，而BlueNet皮網(wǎng)間需要借助從節(jié)點進行聯(lián)系，導(dǎo)致皮網(wǎng)間的通路跳數(shù)增加。

33 網(wǎng)絡(luò)可靠性

網(wǎng)絡(luò)可靠性評估的傳統(tǒng)做法是從圖論角度研究網(wǎng)絡(luò)拓撲的連通性，如果網(wǎng)絡(luò)存在這樣一個節(jié)點，當把所有與它相連的邊刪除后，網(wǎng)絡(luò)被劃分為兩個不相交的子圖，則該節(jié)點為割點。可以用割點的數(shù)量來評估網(wǎng)絡(luò)的可靠性，割點數(shù)量越多網(wǎng)絡(luò)越不可靠，如BlueTree算法生成的拓撲結(jié)構(gòu)是一種樹型結(jié)構(gòu)，其主干節(jié)點全都是割點，網(wǎng)絡(luò)的可靠性最差，而且容易出現(xiàn)通信瓶頸。

圖8和9分別是BGN和BlueNet算法所生成的分散網(wǎng)中主干節(jié)點的割點數(shù)及割點與主干節(jié)點的百分比。可以看到，割點的數(shù)量隨著節(jié)點數(shù)量的增加而逐步減少，如BGN(θ=2)在70個節(jié)點時，主干節(jié)點中割點大約有62.2%，而在250個節(jié)點時只有13.6%。這是因為單位面積內(nèi)節(jié)點密度增大進一步提高了網(wǎng)絡(luò)的連通度。

盡管BlueNet的主干節(jié)點割點數(shù)量比BGN少，但BGN采用的是在主干節(jié)點預(yù)留位置的辦法來構(gòu)建冗余鏈接，而BlueNet則是算法的第三階段，用從節(jié)點做橋節(jié)點，且沒有對冗余鏈接進行控制，導(dǎo)致主干節(jié)點劇增（參見圖6）。相比之下，BGN算法能夠在保持網(wǎng)絡(luò)一定程度的冗余鏈接的同時避免浪費過多的網(wǎng)絡(luò)資源來構(gòu)建冗余鏈接。

34 網(wǎng)絡(luò)最大流量

在無線傳感器網(wǎng)絡(luò)多種應(yīng)用場景中，各節(jié)點需要在短時間內(nèi)將采集數(shù)據(jù)傳輸?shù)絽R聚節(jié)點，由于無線傳感器網(wǎng)絡(luò)往往只有一個匯聚節(jié)點，在上述場景中網(wǎng)絡(luò)數(shù)據(jù)傳輸呈現(xiàn)出一種多對一的匯聚傳輸。給定一個網(wǎng)絡(luò)，由于節(jié)點和鏈路容量的限制，它在單位時間內(nèi)能夠傳輸?shù)男畔⒘渴怯袠O限的，該問題被稱為最大流量問題，可以用FordFulkerson算法［11］求近似解。

圖10給出了BlueTree、BlueNet和BGN算法（θ=2）在各種并發(fā)數(shù)下所構(gòu)建分散網(wǎng)的最大流量近似值。實驗環(huán)境如下：N(=40)個節(jié)點隨機分布在20×20的場景中，節(jié)點的通信半徑R=10 m。設(shè)所有鏈路的帶寬為B0=1 000 kbps，主節(jié)點每擁有一個從節(jié)點需要消耗B1=10 kbps帶寬，橋節(jié)點每連接一個子網(wǎng)需要消耗100 kbps帶寬，則節(jié)點i的通信容量計算式為

Ci=B0i∈slave

B0-nisB1-(nib-1)B2i∈master (2)

其中：如果節(jié)點i是主節(jié)點，則nis表示它所控制的從節(jié)點數(shù)量，nib表示它所連接的皮網(wǎng)數(shù)。

從圖10可以看到，BlueTree的網(wǎng)絡(luò)最大傳輸容量最小，在單數(shù)據(jù)流時網(wǎng)絡(luò)的最大流量約為400 kbps，而在多數(shù)據(jù)流時網(wǎng)絡(luò)的最大流量達到1 285.7 kbps。這是因為BlueTree是一種樹型拓撲結(jié)構(gòu)，容易出現(xiàn)數(shù)據(jù)傳輸瓶頸。而BlueNet和BGN都是網(wǎng)狀拓撲結(jié)構(gòu)，其最大傳輸容量都優(yōu)于BlueTree。其中BlueNet在單數(shù)據(jù)流時網(wǎng)絡(luò)最大流量為642.8 kbps，在多數(shù)據(jù)流時網(wǎng)絡(luò)的最大流量為1 750 kbps。而BGN在單數(shù)據(jù)時網(wǎng)絡(luò)最大流量比BlueNet稍差，大約只有535.7 kbps，但隨著并發(fā)數(shù)據(jù)流的增加，其性能越來越接近BlueNet。

盡管BGN算法的網(wǎng)絡(luò)最大流量稍遜于BlueNet，但BGN算法在主干節(jié)點數(shù)量和平均路徑長度和網(wǎng)絡(luò)可靠性方面都優(yōu)于BlueNet算法。

4 結(jié)束語 

藍牙是一種先進的、低功耗的近距離無線通信技術(shù)，越來越多的無線傳感器節(jié)點使用它來組網(wǎng)，藍牙分散網(wǎng)的結(jié)構(gòu)在很大程度上決定了路由協(xié)議的性能，而橋節(jié)點的數(shù)量和每個橋節(jié)點的度是決定藍牙分散網(wǎng)路由性能的重要因素。本文提出一種新的藍牙分散網(wǎng)結(jié)構(gòu)，該結(jié)構(gòu)能在橋節(jié)點數(shù)量與藍牙生長樹相同的情況下增加橋節(jié)點的度，改善網(wǎng)絡(luò)的可靠性和負載能力。仿真實驗的結(jié)果表明，該協(xié)議在主干節(jié)點數(shù)量、平均路徑長度、網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)最大傳輸流量方面具有優(yōu)勢。

下一步將在BGN算法基礎(chǔ)上對數(shù)據(jù)匯聚問題作深入研究，并考慮部分節(jié)點移動、失效等因素引起的更復(fù)雜的問題。

參考文獻：

［1］

JONES C E，SIVALINGAM K M，AGRAVAL P，et al.A survey of energy efficient network protocols for wireless networks[J].Wireless Networks，2001，7(4)：343358.

［2］ZARUBA G V，BASAGNI S，CHLAMTAC I.BlueTrees：scatternet formation to enable bluetoothbased Ad hoc networks[C]//Proc of IEEE International Conference on Cominunications.2001:273277.

［3］WANG Zhifang，THOMAS R J，HAAS Z.BlueNet:a new scatternet formation scheme [C]//Proc of the 35th Hawaii International Conference on System Science.2002:6169.

［4］SAGINBEKOV S，KORPEOGLU I.An energyefficient scatternet formation algorithm for bluetoothbased sensor networks[C]//Proc of the 2nd European Workshop on Wireless Sensor Networks.2005.

［5］SONG W Z，LI X Y，WANG Y，et al.dBBlue: low diameter and selfrouting bluetooth scatternet [J].Parallel Distribute Computing，2005，65(2):178190.

［6］CHANG C Y，YU G J，LIN Chingfeng，et al.Relayreduction and route construction for scatternet over bluetooth radio systems[C]//Proc of the 16th International Conference on Information Networking.2002:5B2.110.

［7］楊帆，王珂，錢志鴻.鏈形結(jié)構(gòu)的藍牙分散網(wǎng)拓撲構(gòu)成算法與性能仿真 [J].通訊學報，2006，27(1):2835.

［8］MOH M，DUMONT M，MOH T S.Evaluation of dynamic treebased data gathering algorithms for wireless sensor networks[C]//Proc of the 5th IEEE International Symposium on Signal Processing and Information Technology.2005:170175.

［9］XIE Rong，QI Deyu，LI Yongjun，et al.A novel distributed MCDS approximation algorithm for wireless sensor networks [J].Wireless Communications and Mobile Computing，2007，7(8):26632666.

［10］LBL，XEROX PARC，UCB，USC/ISI.The network simulator:ns2[EB/OL].http://www.isi.edu/nsnam/ns/.

［11］JONES R H，STEELE N C.Mathematics in communication theory[M].Ellis Horwood:Halsted Press，1989.