在多躍轉接隨意網路(multihop ad hoc networks)中,為達到最大的空間利用率(spatial reuse),避免封包碰撞(packet collision)以及提供服務品質(quality of service,QoS)保證,一般是利用網路拓樸(network topology)的訊息來設計傳送排程演算法(transmission scheduling algorithm).因此,當網路拓樸改變時,這些具網路拓樸依賴性(topology-dependent)的傳送排程演算法也須隨之做調整.由於此一特性,使得具網路拓樸依賴性的傳送排程演算法在高度移動性的環境中無法得到預期的系統效能.當網路拓樸改變時,為避免重新計算以及安排時槽(time slot),在文獻中已有網路拓樸透明化(topology-transparent)傳送排程演算法的提出.在本論文中,將研究並設計網路拓樸透明化的傳送排程演算法.不同以往大多之文獻假設,本論文考慮較符合實際情況的干擾模式(interference model),即干擾範圍(interference range)大於通訊範圍(communication range).在此干擾模式假設下,將利用組合區塊設計理論(combinatorial block design)來設計網路拓樸透明化的傳送排程演算法,其中包含主機傳送(node activation)和鏈結傳送(link activation).
針對採用分時多重進接(time-division multiple-access,TDMA)的多躍轉接隨意網路,為了提供每一主機(node)服務品質的保證,論文中提出網路拓樸透明化的主機傳送排程演算法.根據balanced incomplete block(BIB)design的特性,可設計兩種不同的對映方式(mapping):mapping I和mapping II,將BIB design理論應用到網路拓樸透明化的主機傳送排程設計領域中.此兩種對映方式均可保證每一個主機在一個訊框(frame)的時間內可以將封包(packet)成功地傳送到任何一個下一個接收點(next-hop receiver).在這兩種對映方式下,探討幾種不同的BIB design 建構方式並提出實際的演算法.由理論分析結果得知,論文中所提出方法的效能均可優於文獻中的網路拓樸透明化的主機傳送排程演算法.同時,也可由研究結果中發現到:由mapping II所得到throughput效能會比mapping I的高;但mapping II的訊框長度卻通常會比mapping I長.
針對採用分碼多重進接(code-division multiple-access,CDMA)的多躍轉接隨意網路,為提供每一鏈結(link)服務品質的保證,論文中提出網路拓樸透明化的鏈結傳送排程演算法.根據resolvable balanced incomplete block (RBIB) design以及group divisible (GD) design的數學特性,設計對映方式將RBIB design以及GD design理論應用到網路拓樸透明化的鏈結傳送排程設計領域中,使得每一個鏈結均可在一個訊框的時間內可以將封包成功地傳送到特定一個下一個接收點(next-hop receiver).論文中將分別探討一種RBIB design以及一種GD design 的建構方式.由理論分析結果得知,論文中所提出的方法其效能均優於文獻中的網路拓樸透明化的鏈結傳送排程演算法.

Many topology-dependent transmission scheduling algorithms, which assume exact network　topology information and require recomputations when the network topology changes, have　been proposed to maximize the spatial reuse and minimize the transmission schedule frame length in multihop ad hoc networks. In the highly dynamic mobile environments, the need for constant adaptation to the changes in network topology makes the topology-dependent algorithms become less efficient. Hence, topology-transparent transmission scheduling algorithms which reduce the burden of having to recompute and reassign time slots have received attention. In this dissertation, topology-transparent transmission scheduling protocols for multihop ad hoc networks are studied. An interference model which captures the difference between transmission and interference ranges is considered. Under this interference model, topology-transparent scheduling schemes, including node activation and link activation, are proposed based on the theory of combinatorial block design.
Topology-transparent node activation transmission scheduling protocols focus on quality-of-service (QoS) provisioning for each node in a multihop time-division multiple-access (TDMA) ad hoc network. With the properties of balanced incomplete block (BIB) designs, there are two methods (called mapping I and mapping II ) to apply the theory of BIB designs to the topology-transparent node activation scheduling. Both methods guarantee conflict-free transmission slots for each node in each frame. Under these two mapping methods, several series of BIB design constructions are studied and evaluated. Based on the results derived, topology-transparent node activation scheduling algorithms are presented. The proposed node activation schemes maximize the minimum system throughput,
and analysis results show that the proposed algorithms outperform existing algorithms. In particular, among the proposed node activation scheduling algorithms, the minimum system throughput obtained under mapping II method is better than that obtained under mapping I method at the expense of longer schedule frames.
Topology-transparent link activation transmission scheduling protocols focus on QoS provisioning for each communication link in a multihop code-division multiple-access (CDMA) ad hoc network. Topology-transparent link activation scheduling frameworks are presented based on the theory of resolvable balanced incomplete block (RBIB) designs and the theory of group divisible (GD) designs. By mathematical properties of RBIB designs and GD designs, the proposed frameworks guarantee conflict-free transmission slots for each communication link in each frame. With the proposed frameworks, one series of RBIB design constructions and one series of GD design constructions are studied and evaluated. Based on the results derived, topology-transparent link activation scheduling algorithms are then presented. The proposed link activation schemes are designed for different objectives: maximizing the minimum system throughput and/or minimizing the schedule frame length. Analysis results show that the proposed algorithms outperform previously known schemes.

[1] IEEE Computer Society,“802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,”1999.
[2] IEEE 802.11 WG,“Draft Supplement to STANDARD for Telecommunications and Information Exchange Between Systems - LAN/MAN Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS),”IEEE Std 802.11e/D8.0, Feb. 2004.
[3] G. Chakraborty,“Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks,”IEEE Trans. Commun., vol. 52, no. 5, pp. 765–777, May 2004.
[4] I. Chlamtac and A. Lerner,“Fair algorithms for maximal link activation in multihop radio networks,”IEEE Trans. Commun., vol. 35, no. 7, pp. 739–746, Jul. 1987.
[5] I. Chlamtac and S. Pinter,“Distributed nodes organization algorithm for channel access in a multihop dynamic radio network,”IEEE Trans. Computers, vol. 36, no. 6, pp. 728–737, Jun. 1987.
[6] I. Cidon and M. Sidi,“Distributed assignment algorithms for multihop packet radio networks,”IEEE Trans. Computers, vol. 38, no. 10, pp. 1353–1361, Oct. 1989.
[7] A. Ephremides and T. V. Truong,“Scheduling broadcasts in multihop radio networks,”IEEE Trans. Commun., vol. 38, pp. 456–460, Apr. 1990.
[8] N. Funabiki and Y. Takefuji,“A parallel algorithm for broadcast scheduling problems in packet radio networks,”IEEE Trans. Commun., vol. 41, pp. 828–831, Jun. 1993.
[9] B. Hajek and G. Sasaki,“Link scheduling in polynomial time,”IEEE Trans. Inform. Theory, vol. 34, pp. 910–917, Sep. 1988.
[10] B. Hajek,“Balanced scheduling in a packet synchronized spread spectrum network,”in Proc. IEEE Infocom, pp. 56–65, 1983.
[11] J. L. Hammond and H. B. Russell, Properties of a ransmission assignment algorithm for multiple-hop packet adio networks,”IEEE Trans. Wireless Commun., vol. 3, no. 4, pp. 1048–1052, Jul. 2004.
[12] A. S. Kershenbaum and M. J. Post,“Distributed scheduling of CDMA networks with minimal information,”IEEE Trans. Commun., vol. 39, pp. 17–20, Jan. 1991.
[13] C. Y. Ngo and V. O. K. Li,“Centralized broadcast scheduling in packet radio networks via genetic-fix algorithms,”IEEE Trans. Commun., vol. 51, no. 9, pp. 1439–1441, Sep. 2003.
[14] M. J. Post, A. S. Kershenbaum, and P. E. Sarachik,“Scheduling multihop CDMA networks in the presence of secondary conflicts,”Algorithmica., vol. 28, no. 3, pp. 365–393, Dec. 1989.
[15] C. G. Prohazka,“Decoupling link scheduling constraints in multihop packet radio networks,”IEEE Trans. Comput., vol. 38, pp. 455–458, Mar. 1989.
[16] R. Ramaswami and K. K. Parhi,“Distributed scheduling of broadcasts in a radio network,”in Proc. IEEE Infocom, pp. 497–504, 1989.
[17] S. Ramaswami and E. L. Lloyd,“Scheduling algorithms for multihop radio networks,”IEEE/ACM Trans. Networking, vol. 1, no. 2, pp. 166–177, Apr. 1993.
[18] S. Salcedo-Sanz, C. Bousono-Calzon, and A. R. Figueiras-Vidal,“A mixed neuralgenetic algorithm for the broadcast scheduling problem,”IEEE Trans. Wireless Commun., vol. 2, no. 2, pp. 277–283, Mar. 2003.
[19] J. Shor and T. G. Robertazzi,“Traffic sensitive algorithms and performance measures for the generation of self-organizing radio network schedules,”IEEE Trans. Commun., vol. 41, pp. 16–21, Jan. 1993.
[20] G. Wang and N. Ansari,“Optimal broadcast scheduling in packet radio networks using mean field annealing,”IEEE J. Select. Areas Commun., vol. 15, no. 2, pp. 250–260, Feb. 1997.
[21] I. Chlamtac and A. Farago,“Making transmission schedules immune to topology changes in multi-hop packet radio networks,”IEEE/ACM Trans. Networking, vol.
2, no. 1, pp. 23–29, Feb. 1994.
[22] Z. Cai, M. Lu, and C. N. Georghiades,“Topology-transparent time division multiple access broadcast scheduling in multihop packet radio networks,”IEEE Trans. Veh. Technol., vol. 52, no. 4, pp. 970–984, Jul. 2003.
[23] J. H. Ju and V. O. K. Li,“An optimal topology-transparent scheduling method in multihop packet radio networks,”IEEE/ACM Trans. Networking, vol. 6, no. 3, pp. 298–306, Jun. 1998.
[24] J.-H. Youn and B. Bose,“A topology-independent transmission scheduling in multihop packet radio networks,”in Proc. IEEE Globecom, pp. 1918–1922, Nov. 2001.
[25] K. Oikonomou and I. Stavrakakis,“Analysis of topology-unaware TDMA MAC policies for ad-hoc networks under diverse traffic loads,”ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, pp. 25–38, Oct. 2005.
[26] I. Chlamtac, A. Farago, and H. Y. Ahn,“A topology transparent link activation protocol for mobile CDMA radio networks,”IEEE J. Select. Areas Commun., vol. 12, no. 8, pp. 1426–1433, Oct. 1994.
[27] E. M. Rains and N. J. A. Sloane, Table of Constant Weight Binary Codes, available online at www.research.att.com/~jas/codes/Andw/
[28] F. Sivrikaya and Bulent Yener,“Time ynchronization in sensor networks: A survey,”IEEE Network, vol. 18, pp. 45–50, July/Aug. 2004.
[29] J. Elson and D. Estrin,“Time synchronization for wireless sensor networks,”in Proc. 15th International Parallel and Distributed Processing Symposium, pp. 1965–1970, Apr. 2001.
[30] E. S. Sousa and J. A. Silvester,“Spreading code protocols for distributed spread spectrum packet radio networks,”IEEE Trans. Commun., vol. 36, pp. 272–281, Mar. 1988.
[31] A. Dey, Theory of Block Designs. John Wiley & Sons, New York, 1986.
[32] D. Raghavarao, Constructions and Combinatorial Problems in Design of Experiments. John Wiley & Sons, New York, 1971.
[33] E. K. P. Chong and S. H. Zak, An Introduction to Optimization. Interscience, New York: Wiley, second ed., 2001.
[34] S. Furino, Y. Miao, and J. Yin, Frames and Resolvable Designs: Uses, Constructions, and Existence. CRC Press, Boca Raton FL, 1996.
[35] A. P. Street and D. J. Street, Combinatorics of Experimental Design. Clarendon Press, Oxford, 1987.
[36] H. Takagi and L. Kleinrock,“Optimal transmission ranges for randomly distributed packet radio terminals,” IEEE Trans. Commun., vol. 32, pp. 246–257, Mar. 1984.