3.對于算法的節(jié)點插入和移除的兩個過程

　　對于一個被給定的藍牙WPAN拓撲，討論兩種分布式過程來處理拓撲變化。第一個過程是允許在WPAN中插入一個新的節(jié)點;第二個過程是從網(wǎng)絡中去除一個節(jié)點，這兩個過程要達到的主要目標是滿足藍牙規(guī)范的限制條件，即全網(wǎng)絡連通性，有高的吞吐流量，降低控制信息的開銷等。當然，可以加入一個新節(jié)點到網(wǎng)絡中去，也意味著可以同時加入幾個節(jié)點。因此，根據(jù)這個，我們可以依靠最初給定的一系列藍牙設(shè)備用來建立一個可增長的BT--WPAN或者形成一個網(wǎng)絡拓撲。

　　（1）插入節(jié)點過程

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

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

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

　　2位：節(jié)點的流量的等級；

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

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

　　具有少于7個從節(jié)點的主節(jié)點；

　　從節(jié)點；

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

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

　　已經(jīng)具有7個節(jié)點的主節(jié)點；

　　像a一樣也在等著加入到藍牙WPAN中。

　　a根據(jù)以下的優(yōu)先順序來選擇加入到哪個回應節(jié)點；

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

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

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

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

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

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

　　有兩種不同的情況：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　8、新節(jié)點

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

　　移去節(jié)點的過程

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

　　。該節(jié)點是從節(jié)點：該情況最簡單，那就是該節(jié)點僅僅是從網(wǎng)絡中移去，而沒有改變拓撲的任何結(jié)構(gòu)。

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

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

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

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

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

　　小結(jié)

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

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

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