臺灣博碩士論文加值系統

物件追蹤是利用感測節點來追蹤特定物件的所在位置，讓我們可以監控物件的移動情形，對其移動性質做更進一步的分析。在實際追蹤物件時，感測節點應該根據物件移動情形即時進行物件位置更新，以便我們及時監控物件的移動動作。
在缺乏物件移動的統計資料下，我們提出一個藉由數學分析物件移動模型來建樹的方式。此模型將物件在感測節點之間移動的行為定義為馬可夫鏈，並利用隨機程序的數學性質來分析計算出物件的移動模型。經過模擬實驗的結果證實，採用數學分析方式能夠適用在任何的物件移動模型，可以使物件位置資料傳遞所需耗費的成本降到最低。我們也考慮了 DAT 與 MST 兩種不同的建立資料傳遞樹方式，當我們給予不同的物件 mobility profile，會得到差異甚大的結果。
而在降低向感測節點詢問物件資料的成本方面，以數學分析物件在各個節點的停留次數取代統計資料來做節點之間連結的調整，亦有高度的成效。不過對於物件停留節點總次數的選擇，將會對詢問成本造成很大的影響。
綜觀以上結果，以馬可夫鏈建立資料傳遞樹，能夠完全取代傳統以統計資料方式建樹，並且獲得更高的效能。

1 簡介 1
2 背景知識與相關研究 5
2.1 Drain-And-Balance Method……………………………… 5
2.2 Deviation-Avoidance Tree……………………………… 6
2.3 Mobility Models ………………………………………… 9
2.4 Query Cost Reduction ……………………………… 10
3 以馬可夫鏈建立物件移動模型 14
3.1 Maximum Spanning Tree (MST) ………………… 14
3.2 分析Mobility Profile ……………………………… 14
3.3 物件停留在各節點次數的分析計算 ………………… 20
4 模擬與實驗結果 22
4.1 環境參數 ……………………………………………………… 22
4.2 Simulation Flow ………………………………………… 22
4.3 模擬結果 – Update Cost ……………………………… 24
4.4 模擬結果 – Query Cost 與 Total Cost……………… 31
5 結論 36

[1] F. Aurenhammer, ”Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, no. 3, pp. 345-405, Sep. 1991.

[2] C. Bettstetter, ”Smooth is Better than Sharp: A Random Mobility Model for Simulation of Wireless Networks,” in Proc. of 4th ACM International Workshop on Modeling, Analysis, and Simulation of Wireless and Mobile Systems(MSWiM’01), pp. 19-27, Rome, Italy, July 2001.

[3] Michael Gerharz, Christian de Waal, Matthias Frank, and Peter Martini, ”Link Stability in Mobile Wireless Ad Hoc Networks,” in Proc. of IEEE Conference on Local Computer Networks, Nov. 2002.

[4] H.T. Kung and D. Vlah, ”E?cient Location Tracking Using Sensor Networks,”in Proc. of 2003 IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2003.

[5] B. Liang and Z. J. Haas, ”Predictive distance-based mobility management for multidimensionalPCSnetworks,”IEEE/ACM Trans. on Networking, 11:718-732, Oct. 2003.

[6] Chih-Yu Lin, Wen-Chih Peng, and Yu-Chee Tseng, ”E?cient In-Network Moving Object Tracking in Wireless Sensor Networks,” IEEE Trans. on Mobile Computing, to appear.

[7] Marcos Augusto M. Vieira, Luiz Filipe M. Vieira, Linnyer B. Ruiz, Antonio A.F. Loureiro, Antonio O. Fernandes, and Jos′e Marcos S. Nogueira, ”Scheduling Nodes in Wireless Sensor Networks: A Voronoi Approach”, in Proc. of the 28th Annual IEEE International Conference on Local Computer Networks (LCN’03), Oct. 2003.