在本論文中，提出了一個有別於廣度優先搜尋任一廣播位址對應裝置選擇法(Device Anycasting Breadth First Search Approach - DA-BFS)，我們命名為品質優先裝置選擇法(Device Anycasting Quality First Search Approach - DA-QFS)。在無線個人區域網路(Wireless Personal Area Networks)中，裝置(device)具有移動性(mobility)以及能源(energy)是有限的，需求是要以多個不同種類的裝置來完成一件任務，DA-BFS 在任務示意圖(Task Graph)上僅以該種裝置與其某一連線者之間的反應時間(response time)來判斷選擇與否，固然在選擇判斷的花費時間上較少，但在裝置移動速率增加、裝置能源消耗以及使用者人數增加的環境與考量下，DA-BFS 的改善空間便很明顯。
　　DA-QFS 改善了以上的問題，選擇某種裝置時，利用裝置選擇權重演算法(Weighted Instantiation Algorithm - WIA)以該種裝置的所有親代(parents)裝置做選擇考量，並將與該裝置的距離、目前被選取的次數以及各個連線的資料類別納入選擇考量。雖然在做選擇考量上花費較多的時間，但在裝置移動速率增加以及多使用者的環境下，效能評比如：封包延遲時間、封包遺失率、能源消耗量以及裝置重選次數都優於DA-BFS。

　In this thesis, we propose a device searching approach, called Device Anycasting Quality First Search (DA-QFS) approach. In Wireless Personal Area Networks (WPAN), there is already an outstanding algorithm, called Device Anycasting Breadth First Search (DA-BFS) approach, which gets good performance results in less mobility and single user scenario. DA-BFS does save instantiation time in this scenario, but it is still possible to being improved.
　
　Including considerations of number of instantiation, packet types, and device mobility, makes the performance of DA-QFS better than DA-BFS. Via Characterized Task Graph (CTG) and Weighted Instantiation Algorithm (WIA), every device is monitored by its parents and the status of the instantiated devices will be periodically returned to user device to adapt to the changing of the networks due to device mobility. Though the instantiation time of DA-QFS is longer than DA-BFS one, the performance of DA-QFS is better than DA-BFS, especially in multiple users’ and high mobility environment. And even the number of re-instantiation is less than DA-BFS one.

[1]　P. Misra, “Routing Protocols for Ad Hoc Mobile Wireless Networks”, November 1999
[2]　C. E. Perkins and E. Royer, “Ad-Hoc On-Demand Distance Vector Routing”, August 1998
[3]　C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers”, 1994
[4]　IEEE 802.15 Working Group for Wireless Personal Area Networks, http://www.ieee802.org/15/about.html
[5]　C. Partridge, T. Mendez, and W. Milliken, “Host Anycasting Service”, November 1993
[6]　C. Metz, “IP Anycast Point-to-(Any) Point Communication”, March 2002
[7]　E. W. Zegura, Member, IEEE, M. H. Ammar, Senior Member, IEEE, Z. Fei, and S. Bhattacharjee, “Application-Layer Anycasting A Server Selection Architecture and Use in a Replicated Web Service”, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, August 2000
[8]　S. Doi, Osaka University, S. Ata, Osaka City University, H. Kitamura, NEC Corporation, and M. Murata, Osaka University, “IPv6 anycast for simple and effective service-oriented communications”, IEEE Communications Magazine, May 2004
[9]　P. Basu, W. Ke, and T. D.C. Little, “Dynamic Task-Based Anycasting in Mobile Ad Hoc Networks”, Mobile Networks and Applications 8, 593–612, 2003

[10]　Y. K. Kwok and I. Ahmad, “Benchmarking the Task Graph Scheduling Algorithms”, Proceedings of the 12th. International Parallel Processing Symposium, 1998
[11]　C. D., Polychronopoulos, “The Hierarchical Task Graph and its Use in Auto-Scheduling”, Proceedings of the 5th international conference on Supercomputing, 1991
[12]　M. Chatterjee, S. K. Das, and D. Turgut, WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks, Cluster Computing 5, 193–204, 2002
[13]　S. Basagni, I. Chlamtac and A. Farago, A generalized clustering algorithm for peer-to-peer networks, in: Proceedings of Workshop on Algorithmic Aspects of Communication (satellite workshop of ICALP), July 1997
[14]　I. Chlamtac and A. Farago, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks 5(3) (August 1999) 149–156.
[15]　E.H.-K.Wu, J.T.-C. Tsai, and M. Gerla, The effect of radio propagation on multimedia, mobile, multi-hop networks: models and countermeasures, in: Proceedings of IEEE Singapore International Conference on Networks, SICON’97.
[16]　J. Broch, D.A. Maltz, D.B. Johnson, Y.C. Hu, and J. Jetcheva, A performance comparison of multi-hop ad hoc network routing protocols, in: Proc. of 4th ACM MobiCom, Dallas, TX (1998).