具多重主動機制之藍芽分散網路排程

A Multi-Active Scatternet Scheduling

張俊宜(Chun-I Chang)

指導教授 ： 賴國華 博士

元智大學/資訊學院/資訊工程學系/碩士(2003年)

摘要

Bluetooth原是一種被用來取代cable的低價格與短距離無線技術，並使行動電子裝置可隨機組成一個Piconet點對點網路(Ad hoc network)，然而在某些時候亦需要經由一些稱為bridge節點的特殊裝置轉送資料以形成一個multihop的Bluetooth點對點網路，稱之為Scatternet。一個有效率的Scatternet必須設計一套inter-piconet排程演算法來安排每一個節點的活動時機(active)來進行資料交換。
本論文提出一適用於Bluetooth Scatternet的多重主動排程演算法在hold模式或sniff模式，以約會通訊方式與各節點交換資料，並將多階層排程法與可橋接的Slave排程法合併應用於多階層網路結構和共用Slave網路結構，使其得以適用於大部分的Scatternet網路拓樸，此外，將封包依傳送經過的hop數與即時需求分類，配合隨機過程預測節點間未來通訊時的交通流量狀況，以得到最合適的排程並減輕因一些可用的通訊時槽浪費而導致的效能影響。
模擬結果顯示，在傳送資料的hop數多寡影響上，利用多重主動排程演
算法可以達到85%的最佳效果並減少約20%的封包延遲時間，此外並可增加約12%的電源使用率。

關鍵字

藍芽 ； 排程 ； 分散網路 ； 多重主動 ； 多階層排程 ； 可橋接排程 ； 個人化區域網路

並列摘要

Bluetooth is a low cost and short-range wireless technology that is going to be used as a replacement for cables initially. It also enables portable electronic devices to organize a basic topology called Piconet via an ad hoc manner. However, in due course, there will be a demand for forming multihop ad hoc networks over Bluetooth, referred to as Scatternet, through some units called bridge nodes to relay the data. Efficient Scatternet data flow requires design of inter-piconet scheduling algorithms to arrange active occasion of each node for the exchange of data.
In this thesis, we present a novel online Scatternet scheduling algorithm based on the engagement at which the nodes are active with either hold or sniff mode to exchange data, and it is a scheme of dynamic adjustment in scheduling based on varying workload conditions.
Moreover, on Multi-active Scatternet Scheduling consist of Multi-layer Scheduling (MLS) and Bridgeable Slave Scheduling (BSS) which are adapted for Multi-layer Construction (MLC) and Mutual Slave Construction (MSC) respectively in order to be applied in most of topology formations of Scatternet. On the other hand, the packets are classified according to the number of forwarding hops and real time demand, and furthermore we utilize stochastic process to predict traffic condition of future engagement of nodes for suitable schedules. Finally, we also present some ideas to reduce the effect of wasted communication time issues.
According to the results of simulation, our solution can reach nearly 85% of optimal throughput in forwarding hops and reduce about 20% end-to-end packet latency, and also increase almost 12% energy utility rate.

並列關鍵字

Bluetooth ； Scheduling ； Bluetooth Scatternet ； inter-piconet ； Multi-active ； Multi-layer Scheduling ； Ad hoc network ； Personal Area Network (PAN)

參考文獻

[2] Bhagwat, P. and Segall, A., “A Routing Vector Method (RVM) for Routing in Bluetooth Scatternets,” 1999 IEEE International Workshop, pp. 375 -379, 1999.

[8] Capone, A., Gerla, M., and Kapoor, R., “Efficient Polling Schemes for Bluetooth Picocells,” IEEE ICC’01, June 2001.

[9] Chawla, S., Saran, H., Singh, M.,” QoS based scheduling for incorporating variable rate coded voice in Bluetooth,” IEEE ICC 2001, Vol. 4, pp.1232 -1237 , 2001.

[10] Cherkasova L. and Ciardo G.. “Characterizing Temporal Locality and Its Impact on Web Server Performance,” Computer Communication and Networks, 2000.

[11] Das, A., Ghose, A., Razdan, A., Saran, H., and Shorey, R., “Enhancing Performance of Asynchronous Data Traffic over the Bluetooth Wireless Ad-hoc Network,” IEEE INFOCOM’01, Apr.2001.