在無線感測器網路中，為了確保無碰撞的TDMA 封包傳輸，許多相關研究都將這個問題轉換為圖形理論中的最小著色問題。然而使用最小著色問題這個方法來設計無線傳輸排程的話，沒有辦法有效率地確保低延遲傳輸。這篇論文探究其原因，發現傳統著色問題中會出現一個現象，此論文將之名為“隱藏格現象”。傳統著色問題中對於每個節點都只著一個顏色，然而實際上每個節點其實可以著多種顏色且依然滿足著色的條件限制。當將著色問題應用到TDMA 無線傳輸排程時，每種顏色對應到一個時間閘。因此對於每個節點而言，這些額外可著的顏色相應地表示該節點可分配到額外的時間閘。若這些時間閘皆能適當地分配，則可達成降低傳輸延遲的效果。

這篇論文研究了隱藏格現象，並提出一種能找出所有隱藏格的方法。據此，此論文接著提出兩種鏈結排程機制(link scheduling)。第一個機制名為DCLS ，該機制分別考慮每個時間閘的網路拓樸，在每個拓樸中找出數組擁有無碰撞特性的傳輸鏈結。根據分析，DCLS 在延遲複雜度方面的表現優於傳統套用著色概念的機制，且執行時間複雜度相當於網路的直徑。根據實驗模擬結果，在不同的網路密度下，DCLS 能有效降低傳輸延遲。此論文提出的第二個機制名為GSA，該機制能找出並分配所有的隱藏時間閘。實驗模擬結果顯示GSA 相較於傳統的著色方法，能降低一半的傳輸延遲。

此篇論文的第二部份探討了在單一碟形圖 (unit disk graph) 中加入新節點後，圖中最大鄰點數增加值的最小上限。這部份的研究首先介紹在單一碟形圖中
加入新節點後的一些結構特性，接著證明了前述的最小上限，並將該上限表示為加入節點前最大相鄰數的函數。近一步的研究結果推導出了一個出現最小上限時的必要條件，該條件為圖中必須要有六個以上的互不相連子集合。最後，這項研究提供了無線網路中的一個範例。此研究可應用到無線感測器網路、行動任意網路以及包含移動平台之無線網路中的排程機制。

In order to guarantee collision-free transmissions in TDMA-based wireless sensor networks, a substantial amount of work in literature has been done by modeling the problem into the minimum graph coloring. However, such approach is not effective towards low-latency transmissions due to the hidden square phenomenon. The graph coloring approach paints each node with single color, but in fact each node can have multiple colors and still satisify the coloring constraint. When applied the coloring method in wireless scheduling, these additional color assignments, now associated with the time slot assignments, can reduce the data buffering delay.

This thesis studies the hidden square phenomenon, and accordingly proposes methods to identify all hidden squares. With these methods, two link scheduling schemes are proposed. The first scheme is named DCLS, a distributed collision-free low-latency link scheduling. The scheme considers the network snapshot at each time slot, and determines a set of collision-free links on each snapshot. With DCLS, the delay is asymptotically smaller than that with the graph coloring model, and the running time complexity on each snapshot is O(diam), where diam is the diameter of the network graph. From the simulation result, the delay is significantly reduced in the network of maximum degree ranged from 6 to 18, and the duty cycle is 0.23 in average. The second scheme, named GSA, is a greedy slot assignment scheme. GSA is capable of assigning all feasible time slots to each node in the network, and the simulation results have shown that it is possible to reduce the delay of conventional coloring approach in half.

The second part of this thesis considers the problem of the upper bound of the maximum degree on inserting vertices in unit disk graphs. This study first introduces the underlying structural properties of UDG insertions, and then proves a least upper bound as the function of the previous maximum degree. Further, the results of this study lead to a surprising necessary condition in the presence of the upper bound, showing that the network should have at least six disconnected components. Finally, the case study gives
examples in wireless networks. Applications of the proposed problem include, but not limit to, the scheduling protocols in wireless sensor networks, mobile ad hoc networks, and wireless networks with mobile stations.

[1] I. Demirkol, C. Ersoy, and F. Alagoz, “MAC Protocols for Wireless Sensor Networks:
a Survey,” IEEE Communications Magazine, vol. 44, no. 4, pp. 115–121, Apr. 2006.
[2] S. Ramanathan and E. L. Lloyd, “Scheduling Algorithms for Multihop Radio Networks,”
IEEE/ACM Transactions on Networking, vol. 1, no. 2, pp. 166–177, Apr.
1993.
[3] Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,
IEEE 802 LAN/MAN Standards Commitee, 1999.
[4] D. B. West, Introduction to Graph Theory. Prentice-Hall, 2001.
[5] I. Slama, B. Jouaber, and D. Zeghlache, “A Free Collision and Distributed Slot
Assignment Algorithm for Wireless Sensor Networks,” in Proceedings of IEEE Global
Telecommunications Conference (GLOBECOM’08), Dec. 2008, pp. 1–6.
[6] S. Gandham, M. Dawande, and R. Prakash, “Link Scheduling in Sensor Networks:
Distributed Edge Coloring Revisited,” in Proceedings of IEEE Annual Joint Conference
of IEEE Computer and Communications Societies (INFOCOM’05), vol. 4, Mar.
2005, pp. 2492–2501.
[7] C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, S. Thite, and S. Thulasidasan,
“Strong Edge Coloring for Channel Assignment in Wireless Radio Networks,”
in Proceedings of Annual IEEE International Conference on Pervasive Computing
and Communications Workshops (PERCOMW’06), Mar. 2006, pp. 105–110.
[8] V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, “Energy-Efficient
Collision-Free Medium Access Control for Wireless Sensor Networks,” in Proceedings
of International Conference on Embedded Networked Sensor Systems (SenSys’03),
Nov. 2003, pp. 181–192.
[9] Y.Wang and I. Henning, “A Deterministic Distributed TDMA Scheduling Algorithm
for Wireless Sensor Networks,” in Proceedings of IEEE Internation Conference on
Wireless Communications, Networking and Mobile Computing (WICOM’07), Sept.
2007, pp. 2759–2762.
[10] I. Rhee, A. Warrier, J. Min, and L. Xu, “DRAND: Distributed Randomized TDMA
Scheduling for Wireless Ad-Hoc Networks,” IEEE Transactions on Mobile Computing,
vol. 8, no. 10, pp. 1384–1396, Oct. 2009.
[11] S. H. Wu, M. S. Chen, and C. M. Chen, “Fully Adaptive Power Saving Protocols for
Ad Hoc Networks Using the Hyper Quorum System,” in Proceedings of International
Conference on Distributed Computing Systems (ICDCS’08), June 2008, pp. 785–792.
[12] J. R. Jiang, Y. C. Tseng, C. S. Hsu, and T. H. Lai, “Quorum-Based Asychronous
Power-Saving Protocols for IEEE 802.11 Ad Hoc Networks,” Mobile Networks and
Applications, vol. 10, no. 1-2, pp. 169–181, Feb. 2005.
[13] J. Ma, W. Lou, Y. Wu, X.-Y. Li, and G. Chen, “Energy Efficient TDMA Sleep
Scheduling in Wireless Sensor Networks,” in Proceedings of Conference on Computer
Communications (INFOCOM ’09), Apr. 2009, pp. 630–638.
[14] H. A. B. F. de Oliveira, A. Boukerche, E. F. Nakamura, and A. A. F. Loureiro, “An
Efficient Directed Localization Recursion Protocol for Wireless Sensor Networks,”
IEEE Transactions on Computers, vol. 58, no. 5, pp. 677–691, May 2009.
[15] J. Kang, Y. Zhang, and B. Nath, “TARA: Topology-Aware Resource Adaptation
to Alleviate Congestion in Sensor Networks,” IEEE Transactions on Parallel and
Distributed Systems, vol. 18, no. 7, pp. 919–931, July 2007.
[16] F. Ye, G. Zhong, S. Lu, and L. Zhang, “GRAdient Broadcast: A Robust Data
Delivery Protocol for Large Scale Sensor Networks,” Wireless Networks, vol. 11,
no. 3, pp. 285–298, May 2005.
[17] A. Mei and J. Stefa, “Routing in Outer Space: Fair Trafc Load in Multi-Hop Wireless
Networks,” in Proceedings of ACM International Symposium on Mobile Ad Hoc
Networking and Computing (MobiHoc’08), May 2008, pp. 23–32.
[18] S. C. H. Huang, P. J. Wan, J. Deng, and Y. S. Han, “Broadcast Scheduling in
Interference Environment,” IEEE Transactions on Mobile Computing, vol. 7, no. 11,
pp. 1338–1348, Nov. 2008.
[19] B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit Disk Graphs,” Discrete
Mathematics, vol. 86, no. 1-3, pp. 165–177, Dec. 1990.
[20] M. V. Marathe, H. Breu, H. B. H. Iii, S. S. Ravi, and D. J. Rosenkrantz, “Simple
Heuristics for Unit Disk Graphs,” Networks, vol. 25, no. 2, pp. 59–68, 1995.
[21] H. Garcia-Molina and D. Barbara, “How to Assign Votes in a Distributed System?”
Journal of the ACM (JACM), vol. 32, no. 4, pp. 841–860, Oct. 1985.
[22] S. Y. Cheung, M. Ahamad, and M. H. Ammar, “The Grid Protocol: a High Performance
Scheme for Maintaining Replicated Data,” in Proceedings of International
Conference on Data Engineering, Feb. 1990, pp. 438–445.
[23] H. Kakugawa, S. Kamei, and T. Masuzawa, “A Token-Based Distributed Group
Mutual Exclusion Algorithm with Quorums,” IEEE Transactions on Parallel and
Distributed Systems, vol. 19, no. 9, pp. 1153–1166, Sept. 2008.
[24] M. Mahdian, “The Strong Chromatic Index of Graphs,” Master’s thesis, Department
of Computer Science, University of Toronto, 2000.
[25] M. Molloy and B. Reed, “A Bound on the Strong Chromatic Index of a Graph,”
Journal on Combinatorial Theory, Series B, vol. 69, no. 2, pp. 103–109, Mar. 1997.
[26] M. Luby, “A Simple Parallel Algorithm for the Maximal Independent Set Problem,”
in Proceedings of ACM Symposium on Theory of Computing (STOC’85), Dec. 1985,
pp. 1–10.
[27] N. A. Lynch, Distributed Algorithms. Morgan Kaufmann, 1996.
[28] P. Flajolet, D. Gardy, and L. Thimonier, “Birthday Paradox, Coupon Collectors,
Caching Algorithms and Self-Organizing Search,” Discrete Applied Mathematics,
vol. 39, no. 3, pp. 207–229, Nov. 1992.
[29] A. Kanzaki, T. Hara, and S. Nishio, “An Adaptive TDMA Slot Assignment Protocol
in Ad Hoc Sensor Networks,” in Proceedings of ACM Symposium on Applied
Computing, Mar. 2005, pp. 1160–1165.
[30] I. Chlamtac and A. Farag´o, “Making Transmission Schedules Immune to Topology
Changes in Multi-hop Packet Radio Networks,” IEEE/ACM Transactions on Networking,
vol. 2, no. 1, pp. 23–29, 1994.
[31] S. Boztas, “A Robust Multi-Priority Topology-Independent Transmission Schedule
for Packet Radio Networks,” Information Processing Letters, vol. 55, no. 5, pp. 291–
295, 1995.
[32] V. R. Syrotiuk, C. J. Colbourn, and A. C. Ling, “Topology-Transparent Scheduling
for MANETs Using Orthogonal Arrays,” in Proceedings of Joint Workshop on
Foundations of Mobile Computing (DIALM-POMC ’03), Sept. 2003, pp. 43–49.
[33] T. Herman and S. Tixeuil, “A Distributed TDMA Slot Assignment Algorithm for
Wireless Sensor Networks,” Algorithmic Aspects of Wireless Sensor Networks, pp.
45–58, July 2004.
[34] F. Farnoud and S. Valaee, “Reliable Broadcast of Safety Messages in Vehicular
Ad Hoc Networks,” in Proceedings of Conference on Computer Communications
(INFOCOM ’09), Apr. 2009, pp. 226–234.
[35] S. Basagni and D. Bruschi, “A Logarithmic Lower Bound for Time-Spread Multiple-
Access (TSMA) Protocols,” Wireless Networks, vol. 6, no. 2, pp. 291–295, May 2000.
[36] A. E. F. Clementi, A. Monti, and R. Silvestri, “Distributed Broadcast in Radio
Networks of Unknown Topology,” Theoretical Computer Science, vol. 302, no. 1-3,
pp. 337–364, 2003.