3.對(duì)于算法的節(jié)點(diǎn)插入和移除的兩個(gè)過(guò)程

　　對(duì)于一個(gè)被給定的藍(lán)牙WPAN拓?fù)?，討論兩種分布式過(guò)程來(lái)處理拓?fù)渥兓５谝粋€(gè)過(guò)程是允許在WPAN中插入一個(gè)新的節(jié)點(diǎn);第二個(gè)過(guò)程是從網(wǎng)絡(luò)中去除一個(gè)節(jié)點(diǎn)，這兩個(gè)過(guò)程要達(dá)到的主要目標(biāo)是滿(mǎn)足藍(lán)牙規(guī)范的限制條件，即全網(wǎng)絡(luò)連通性，有高的吞吐流量，降低控制信息的開(kāi)銷(xiāo)等。當(dāng)然，可以加入一個(gè)新節(jié)點(diǎn)到網(wǎng)絡(luò)中去，也意味著可以同時(shí)加入幾個(gè)節(jié)點(diǎn)。因此，根據(jù)這個(gè)，我們可以依靠最初給定的一系列藍(lán)牙設(shè)備用來(lái)建立一個(gè)可增長(zhǎng)的BT--WPAN或者形成一個(gè)網(wǎng)絡(luò)拓?fù)洹?/p>

　?。?）插入節(jié)點(diǎn)過(guò)程

　　一個(gè)節(jié)點(diǎn)想快速加入到WPAN中來(lái)，它必須首先發(fā)送一個(gè)普通的查詢(xún)信息來(lái)懇求它附近的節(jié)點(diǎn)是否可以加入。相反，如果一個(gè)節(jié)點(diǎn)的目的是加入到一個(gè)網(wǎng)絡(luò)中并有良好連接，即想加入到具有低流量的微微網(wǎng)中或者扮演一個(gè)特殊的角色，它就必須使用專(zhuān)用的查詢(xún)。

　　下面部分，討論承載查詢(xún)回復(fù)的FHS包。注意到，一個(gè)數(shù)據(jù)包FHS它包含有設(shè)備類(lèi)型的標(biāo)記，加上5比特就能夠用于傳遞未來(lái)的信息。這其中2位比特預(yù)留下來(lái)以備將來(lái)使用，AM-ADDR領(lǐng)域的3位在查詢(xún)回應(yīng)中不使用。我們定義這5位傳送以下信息：

　　2位：電池的電量等級(jí)（如：低于25%，在25%和50%之間，在50%到75%之間，高于75%）；

　　2位：節(jié)點(diǎn)的流量的等級(jí)；

　　1位：這個(gè)節(jié)點(diǎn)是否屬于孤立微微網(wǎng)。如果一個(gè)微微網(wǎng)沒(méi)有于任何一個(gè)微微網(wǎng)連接或者它附近的微微網(wǎng)都只僅僅與它相連那我們就稱(chēng)之為孤立的微微網(wǎng)。如果該節(jié)點(diǎn)屬于孤立的微微網(wǎng)，那么該位置1，否則置0。

　　設(shè)a是開(kāi)始查詢(xún)過(guò)程的節(jié)點(diǎn)，正如上所述，根據(jù)收到的鄰近的節(jié)點(diǎn)的回應(yīng)，a它將決定對(duì)哪個(gè)節(jié)點(diǎn)進(jìn)行尋呼，回應(yīng)的節(jié)點(diǎn)要么是屬于孤立的徽微網(wǎng)要么不屬于孤立的微微網(wǎng)。除此之外，它還具有以下可能：

　　具有少于7個(gè)從節(jié)點(diǎn)的主節(jié)點(diǎn)；

　　從節(jié)點(diǎn)；

　　即是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)；

　　即是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)；

　　已經(jīng)具有7個(gè)節(jié)點(diǎn)的主節(jié)點(diǎn)；

　　像a一樣也在等著加入到藍(lán)牙WPAN中。

　　a根據(jù)以下的優(yōu)先順序來(lái)選擇加入到哪個(gè)回應(yīng)節(jié)點(diǎn)；

　　1）屬于孤立的微微網(wǎng)主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)）

　　如果a收到不止一個(gè)屬于孤立微微網(wǎng)的主節(jié)點(diǎn)的回應(yīng)，它將選擇從節(jié)點(diǎn)少于7個(gè)和低流量的的主節(jié)點(diǎn)加入。如果不止一個(gè)主節(jié)點(diǎn)滿(mǎn)足上述條件，那么它還根據(jù)該節(jié)點(diǎn)的電池電量的等級(jí)來(lái)考慮。注意到a節(jié)點(diǎn)根據(jù)相關(guān)的RSSI估計(jì)每個(gè)回應(yīng)節(jié)點(diǎn)的距離。把被選擇的主節(jié)點(diǎn)記為u，節(jié)點(diǎn)a尋呼u并創(chuàng)建一個(gè)新的微微網(wǎng)，此時(shí)“a是主節(jié)點(diǎn)，u是從節(jié)點(diǎn)，過(guò)一會(huì)兒，這兩個(gè)節(jié)點(diǎn)的角色進(jìn)行互換，這樣，在微微網(wǎng)中，a就變成從節(jié)點(diǎn)，并且受主節(jié)點(diǎn)u的支配。

　　如果a收到一個(gè)不屬于孤立微微網(wǎng)的節(jié)點(diǎn)的回應(yīng)，它將按如下的方式選擇：

　　1）如果回復(fù)的是從節(jié)點(diǎn)少于7個(gè)的主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)），則a加入此節(jié)點(diǎn)并且創(chuàng)建一個(gè)新的微微網(wǎng)。通過(guò)主從節(jié)點(diǎn)的角色互換，a變成孤立的微微網(wǎng)中的從節(jié)點(diǎn)（或者是橋節(jié)點(diǎn)）

　　2）如果回復(fù)的節(jié)點(diǎn)是從節(jié)點(diǎn)（或者既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)）或者是具有7個(gè)從節(jié)點(diǎn)的主節(jié)點(diǎn)（或者既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)），則“創(chuàng)建一個(gè)新的含有該節(jié)點(diǎn)的微微網(wǎng)。

　　2）屬于孤立的微微網(wǎng)從節(jié)點(diǎn)（或者既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)）

　　有兩種不同的情況：

　　1）沒(méi)有連接到散射網(wǎng)的其它節(jié)點(diǎn)回復(fù)了a的查詢(xún)，在這種情況下，a將有以下的情形：

　?。?）a具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能t容盤(pán)，如果這樣，則a通過(guò)尋呼一個(gè)或多個(gè)對(duì)它的查詢(xún)做過(guò)響應(yīng)的從節(jié)點(diǎn)來(lái)創(chuàng)建一個(gè)新的微微網(wǎng)。那么這些從節(jié)點(diǎn)就成了剛形成的微微網(wǎng)和以前微微網(wǎng)之間的橋節(jié)點(diǎn)。對(duì)于這些被尋呼的從節(jié)點(diǎn)，a可以根據(jù)其節(jié)點(diǎn)的流量、電池狀態(tài)和空間的距離來(lái)選擇。假設(shè)一個(gè)微微網(wǎng)被一短比特位的字符來(lái)標(biāo)識(shí)，即小于5位的長(zhǎng)度，并且在微徽網(wǎng)中的每一個(gè)節(jié)點(diǎn)都知道所在的微微網(wǎng)的標(biāo)識(shí)。一個(gè)被a尋呼的從節(jié)點(diǎn)可以在承載尋呼響應(yīng)的FHS包中利用這’5位來(lái)標(biāo)示這個(gè)信息。這樣，a隨時(shí)有可能中斷尋呼的過(guò)程，因?yàn)樗B接的節(jié)點(diǎn)屬于已經(jīng)有微徽網(wǎng)間連接的節(jié)點(diǎn)。

　?。?）a想成為從節(jié)點(diǎn)。a.根據(jù)流t，電池等級(jí)和空間距離來(lái)選擇可以加入的節(jié)點(diǎn)，它和被選擇的節(jié)點(diǎn)形成一個(gè)新的微微網(wǎng)，然后，在該微微網(wǎng)中，這兩個(gè)節(jié)點(diǎn)互換角色，這樣，。就變成了從節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)則變成了在新微微網(wǎng)和以前微微網(wǎng)之間的主節(jié)點(diǎn)和橋節(jié)點(diǎn)。

　　2）a收到一個(gè)不屬于孤立微微網(wǎng)的的節(jié)點(diǎn)的回復(fù)。在這種情況下，a試圖連接剩余部分散射網(wǎng)中的孤立節(jié)點(diǎn)，并且按照以下優(yōu)先次序在散射網(wǎng)中選擇要連接的節(jié)點(diǎn)：從節(jié)點(diǎn)、既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的節(jié)點(diǎn)、主節(jié)點(diǎn)、既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)、具有7個(gè)從節(jié)點(diǎn)的主節(jié)點(diǎn)。如果有必要，將依照以下準(zhǔn)則進(jìn)一步進(jìn)行選擇：流量，電池等級(jí)，空間距離。然后，完成要選擇的節(jié)點(diǎn)后，a創(chuàng)建一個(gè)新的微微網(wǎng)。

　　3、不屬于孤立的微微網(wǎng)但是又少于7個(gè)從節(jié)點(diǎn)的主節(jié)點(diǎn)

　　在現(xiàn)有的可利用的主節(jié)點(diǎn)之中，。選擇具有最小流量的一個(gè)節(jié)點(diǎn)，如果在流量相同的情況下，然后考慮電池等級(jí)，其次是考慮該節(jié)點(diǎn)離a的空間距離。為了避免微微網(wǎng)之間的重盈和減少微微網(wǎng)內(nèi)部之間的干擾，離“較近的節(jié)點(diǎn)具有優(yōu)先權(quán)。把被選擇的主節(jié)點(diǎn)記為產(chǎn)，節(jié)點(diǎn)a加入聲創(chuàng)建一個(gè)新的微微網(wǎng)，此處a是主節(jié)點(diǎn)，尸是從節(jié)點(diǎn)，過(guò)一會(huì)兒，這兩個(gè)節(jié)點(diǎn)的角色互換，這樣，在微微網(wǎng)中，a變成從節(jié)點(diǎn)，并且受主節(jié)點(diǎn)產(chǎn)的支配。

　　不屬于孤立的微微網(wǎng)從節(jié)點(diǎn)

　　在2的1）中，介紹了它的兩種可能的情況：

　　1）“具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能量，如果這樣，則a通過(guò)尋呼一個(gè)或多個(gè)響應(yīng)過(guò)它的查詢(xún)的節(jié)點(diǎn)來(lái)創(chuàng)建一個(gè)新的微微網(wǎng)，同時(shí)在新的微微網(wǎng)和以前的微微網(wǎng)中的節(jié)點(diǎn)就成為了橋節(jié)點(diǎn)。

　　2）a想成為從節(jié)點(diǎn)。在現(xiàn)有的可以利用的節(jié)點(diǎn)中選擇可以加入的節(jié)點(diǎn)，a和被選擇的節(jié)點(diǎn)形成一個(gè)新的微微網(wǎng)，然后，在該微微網(wǎng)中，這兩個(gè)節(jié)點(diǎn)互換角色，這樣，a就變成了從節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)變成了主節(jié)點(diǎn)和橋節(jié)點(diǎn)。

　　5、不屬于孤立的微微網(wǎng)的既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)

　　像前面所說(shuō)的一樣，它也有兩種可能的情況：

　　l）。具有可以成為主節(jié)點(diǎn)的足夠的處理能力和能量，a依照以下三條準(zhǔn)則來(lái)選擇要尋呼的節(jié)點(diǎn)（該節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)）：流量;電池等級(jí);空間距離。這樣一個(gè)新的微微網(wǎng)形成，此處。作為主節(jié)點(diǎn)而被選擇的節(jié)點(diǎn)作為從節(jié)點(diǎn)。

　　2）a想成為從節(jié)點(diǎn)。在這個(gè)新的微微網(wǎng)中，a作為從節(jié)點(diǎn)，被選擇的節(jié)點(diǎn)作為主節(jié)點(diǎn)而且還充當(dāng)該微微網(wǎng)與它先前所在的微微網(wǎng)的橋節(jié)點(diǎn)。

　　6、不屬于孤立的微微網(wǎng)的既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)

　　在現(xiàn)有的可利用的節(jié)點(diǎn)（既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)）之中，a依照以下三條準(zhǔn)則來(lái)選擇要加入的節(jié)點(diǎn)：流量：電池等級(jí)：空間距離。在a創(chuàng)建一個(gè)新的微微網(wǎng)之后，它與被選擇的節(jié)點(diǎn)互換一下角色，從而在微微網(wǎng)中a成為從節(jié)點(diǎn)并且被它所選擇的節(jié)點(diǎn)（既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)）所支配。

　　7、不屬于孤立的微微網(wǎng)并且已有7個(gè)從節(jié)點(diǎn)的主節(jié)點(diǎn)

　　在現(xiàn)有的可利用的節(jié)點(diǎn)之中，a選擇具有最小流量的一個(gè)節(jié)點(diǎn)，如果在流量相同的情況下，然后考慮電池等級(jí)，其次是考慮該節(jié)點(diǎn)離“的空間距離。以a為主節(jié)點(diǎn)的一個(gè)新的微微網(wǎng)被創(chuàng)建了。此時(shí)有兩種可能性：

　　1）在這個(gè)新的微微網(wǎng)中，a仍然是主節(jié)點(diǎn)，而被選擇的節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn);

　　2）這兩個(gè)節(jié)點(diǎn)互換角色，這樣，被選擇的主節(jié)點(diǎn)使得它的其中的一個(gè)從節(jié)點(diǎn)處于閑置狀態(tài)，該閑置節(jié)點(diǎn)可以運(yùn)行插入程序來(lái)尋找新的微微網(wǎng)以便加入。要不然，a則和在這個(gè)微微網(wǎng)中的其它節(jié)點(diǎn)輪流的處于閑置狀態(tài)。

　　8、新節(jié)點(diǎn)

　　節(jié)點(diǎn)a尋呼到一個(gè)新節(jié)點(diǎn)，這樣創(chuàng)建一個(gè)以a為主節(jié)點(diǎn)的微微網(wǎng)。然后，如果兩個(gè)節(jié)點(diǎn)協(xié)商后，可以互換角色。在該微微網(wǎng)中，同樣可以包含一些回應(yīng)了節(jié)點(diǎn)查詢(xún)的其它節(jié)點(diǎn)。然而，為了保持藍(lán)牙WPAN拓?fù)涞倪B接性，要么是a要么是它微微網(wǎng)中的其它一些節(jié)點(diǎn)必須尋呼現(xiàn)有藍(lán)牙WPAN中節(jié)點(diǎn)。

　　移去節(jié)點(diǎn)的過(guò)程

　　節(jié)點(diǎn)離開(kāi)網(wǎng)絡(luò)引起的變化主要取決于該節(jié)點(diǎn)在藍(lán)牙WPAN中作用，有下面四種情況：

　　。該節(jié)點(diǎn)是從節(jié)點(diǎn)：該情況最簡(jiǎn)單，那就是該節(jié)點(diǎn)僅僅是從網(wǎng)絡(luò)中移去，而沒(méi)有改變拓?fù)涞娜魏谓Y(jié)構(gòu)。

　　。該節(jié)點(diǎn)是主節(jié)點(diǎn)：在該微微網(wǎng)中的從節(jié)點(diǎn)將在藍(lán)牙WPAN中尋找一個(gè)新的節(jié)點(diǎn)來(lái)重新建立連接，因此，每一個(gè)從節(jié)點(diǎn)都要執(zhí)行插入程序，而橋節(jié)點(diǎn)仍然作為橋節(jié)點(diǎn)保持與其它微微網(wǎng)的連接。

　　。該節(jié)點(diǎn)既是主節(jié)點(diǎn)又是橋節(jié)點(diǎn)：這種情況的處理方式與第二種情況的處理方式一樣。

　　。該節(jié)點(diǎn)既是從節(jié)點(diǎn)又是橋節(jié)點(diǎn)：如果有其它節(jié)點(diǎn)可以取代該節(jié)點(diǎn)，那么它就可從網(wǎng)絡(luò)中很簡(jiǎn)單的移去。否則的話(huà)，就必須尋找一個(gè)可以替代該節(jié)點(diǎn)的節(jié)點(diǎn)這樣，在此微微網(wǎng)中主節(jié)點(diǎn)將執(zhí)行查詢(xún)程序，如果不能找到通向目標(biāo)微微網(wǎng)的橋節(jié)點(diǎn)，它將命令它的從節(jié)點(diǎn)執(zhí)行查詢(xún)程序以尋找橋節(jié)點(diǎn)。如果在藍(lán)牙WPAN范圍中，在這些節(jié)點(diǎn)所能傳輸?shù)牡姆秶鷥?nèi)沒(méi)有找到這樣的節(jié)點(diǎn)，那么該微微網(wǎng)就與藍(lán)牙WPAN斷開(kāi)。

　　2.射網(wǎng)的重要性能分析

　　3藍(lán)牙組網(wǎng)的仿真結(jié)果和分析

　　小結(jié)

　　本章介紹了藍(lán)牙個(gè)人區(qū)域網(wǎng)絡(luò)的基本知識(shí)，明確了藍(lán)牙微微網(wǎng)和散射網(wǎng)的概念，分析了藍(lán)牙散射網(wǎng)的網(wǎng)路特點(diǎn)，闡述了藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建的重要性以及藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法需要解決的關(guān)鍵問(wèn)題和衡量藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法的標(biāo)準(zhǔn)。藍(lán)牙自組個(gè)人區(qū)域網(wǎng)絡(luò)的主從特性、動(dòng)態(tài)性、跳頻特性雖然使藍(lán)牙組網(wǎng)更加靈活，但這些特點(diǎn)以及藍(lán)牙節(jié)點(diǎn)本身多為個(gè)人數(shù)字設(shè)備，節(jié)點(diǎn)運(yùn)行的協(xié)議和應(yīng)用程序必須考慮節(jié)點(diǎn)處理能力、內(nèi)存和能耗等條件，都無(wú)疑增加了網(wǎng)絡(luò)拓?fù)錁?gòu)建 算法、網(wǎng)絡(luò)路由等算法的難度。

　　目前藍(lán)牙規(guī)范中對(duì)微微網(wǎng)內(nèi)的通信協(xié)議有了明確的規(guī)定，但對(duì)藍(lán)牙散射網(wǎng)的研究，還處于探索階段，是各國(guó)科學(xué)家感興趣和重點(diǎn)研究的課題之一，越來(lái)越多的研究成果完善了藍(lán)牙網(wǎng)絡(luò)的應(yīng)用，提高了藍(lán)牙產(chǎn)品的普及率。中國(guó)是人口密集，商業(yè)經(jīng)濟(jì)活動(dòng)集中、人均收入還比較低的國(guó)家和地區(qū)，低成本、組網(wǎng)簡(jiǎn)單靈活的藍(lán)牙產(chǎn)品將會(huì)有更廣闊的應(yīng)用前景。它的應(yīng)用將遍及很多領(lǐng)域，如移動(dòng)通信、計(jì)算機(jī)及周邊設(shè)備、個(gè)人隨身信息和娛樂(lè)設(shè)備、網(wǎng)絡(luò)接入設(shè)備、醫(yī)療保健、金融、軍事等。它是面對(duì)個(gè)人的近距離無(wú)線(xiàn)技術(shù)，是人與機(jī)器之間交流的好助手。

　　本章從介紹藍(lán)牙節(jié)點(diǎn)的工作狀態(tài)和藍(lán)牙物理鏈路的建立過(guò)程入手，提出一種備份式的藍(lán)牙散射網(wǎng)拓?fù)錁?gòu)建算法。算法吸收了Bluestars算法中以節(jié)點(diǎn)的可用資源為標(biāo)準(zhǔn)的方法，來(lái)選取主節(jié)點(diǎn)，初始主節(jié)點(diǎn)建立第一個(gè)微微網(wǎng)后，主節(jié)點(diǎn)選取最多3個(gè)橋節(jié)點(diǎn)和3個(gè)次主節(jié)點(diǎn)，通過(guò)逐級(jí)展開(kāi)的方法建立相互連接的微微網(wǎng)，最終形成連通的藍(lán)牙散射網(wǎng)，散射網(wǎng)形成后通過(guò)節(jié)點(diǎn)備份的方法，提高網(wǎng)絡(luò)的自愈能力。本章最后運(yùn)用數(shù)學(xué)推導(dǎo)的方法證明了算法幾項(xiàng)重要的性能指標(biāo)為：時(shí)間復(fù)雜度為O（logN）、消息復(fù)雜度為O（N）、網(wǎng)絡(luò)直徑為O（logN）、具有較少的微微網(wǎng)個(gè)數(shù)和節(jié)點(diǎn)角色的平均數(shù)。