### Paper Menu >>

### Journal Menu >>

Wireless Se n doi:10.4236/ w Copyright © 2 An A T o Depa Abstract Topology-t r throughput modify the the cover-f r Second, w e squashed o u all of its re d put can be transparent mission del Keywords: 1. Introdu Recently, m a monitoring a on Mobile A ties have gr e sion throug h guaranteed Q cations. Since M A and is the ba guaranteed Q pensible [1]. MAC pro t One is the c o known Carr i ance (CSM A its possibili t wireless coll other one is a time fram e *This research i dation of Chin a Basic Disciplin e leum(Beijing) u n sor Network , w sn.2010.2100 9 2 010 SciRes. A lgorit h o polog y rtment of C o m R e r ansparent M guarantee, a cove r -free s r ee se t is pr o e prove that u t. Our algo r d undant slot s guaranteed i node sched u ay can be g o MAC Sche d ction a ny multime d a nd voice rec o A d hoc Netw o e at relationshi p h put and tran s Q oS on MA N A C layer is di r sis of all othe Q oS, guarante t ocols in wir e o ntention- b as e i er Sense M u A /CA) protoc o t y of infinite isions, it can n the scheduli n e is divided in t i s supported in p a (NSFC) under e s Research Fo u u nder grant No.(J C , 2010, 2, 801 9 6 Published O n h m fo r y -Tran s m puter Scienc e ceived June 5 M AC sched u a cove r -free et so that b e o posed and f any subset o r ithm choos e s , and then d e i f the squas h u ling strateg o tten by just u d uling, Qos, C d ia applicatio n o rding, are s u o rks (MANE T p with the gu a s mission del a N ET is requir e r ectly above t r protocols, f o ed QoS on M e less network e d MAC proto u ltiple Access o l as its repr e transmission n o t p rovide Q o n g- b ased MA C t o multiple ti m p art by National N grant No.(6100 u ndation of Chi n C X K -2010-01). -806 n line October 2 r Impr o s paren t C e and Techno Email: xu 5 , 2010; revis e u ling strateg i set is outpu t e tter through p f ound to ha v o f a cove r -f r e s the subset e signates it a h ed subset i s y, both the i u sing our al g C ombinator i n s, such as v u ggested to d e T ). Their feas i a ranteed tran s a y. In other w e d by these a p t he ph y sical l o r a MANET M AC layer is i n are of two t y col, with th e w /Collision A v e sentative. D u delay cause d o S guarantee. C pro t ocol, w m e slots, and N atural Science 3307, 60803159 n a University of 010 (http://ww w o ving T t MA C C haonong X logy, China U u chaonong@ c e d July 12, 2 0 i es nowaday t as scheduli p ut can be g u v e negative i n r ee set is sti which has t h a s the netwo r s adopted as i ncreased m i g orith m as a n i al Design, S v ideo e ploy i bili- s mis- w ord, p pli- l ayer with n dis- y pes. w ell- v oid- u e to d by The w here each no d slo t wh o mis be e S gor i de n the les s eit h no d dep of c mo b p ar e of n app T p ro t p er , N p ro t clu d tho g Foun- ), an d Pet r o- w .SciRP.org/j o hroug h C Sche d X u U niversity of P c up.edu.cn 0 10; accepted s are all ba s ng strategy o u aranteed. A n fluence on ll a cove r -f r h e maximal r k schedulin g network sc h i nimal throu n extra acce s uperimpose d d e is assigned t s [2]. We ta k o se topology sions into di f e liminated ef f S cheduling- b a i zed into two n t and the to p topolog y -dep e s collisions, a h er in every n o d e in centraliz e endent MAC c onstantly ch a b ility of node e nt MAC sc h n etwork topo l licatio ns depl T he scheduled t ocols can be , we focus on N owadays, al l t ocols are all d ing the mult i g onal array [ 8 o urnal/wsn/). h put G u d uling S P etroleum-Be ij August 17, 2 0 s ed on com b o f network. A t the first s t the minima l r ee set after number of r g strategy. T h eduling str a ghput and d s sory. d Code, Cov e the transmitti n k e Figure 1 f is known, b y f ferent time s l f iciently. sed MAC pr o subcategorie s p ology-transp a e ndent MAC p uniform topo l o de in distrib u e d manne r [3 ] protocols are a nged topolo g [4]. On the c o h eduling prot o l ogy and ma y oyed on MA N object of the either wirele node sched ul i l topology-tr a b ased on co m i nomial theo r 8 ], latin squar e u arant S trateg y ij ing, Beijing, 0 10 b inatorial de In this pape r t ep, t he redu n l guarantee d its redunda n r edundant sl o T herefore, be t a tegy. For a n ecreased m a er -Free Set n g right at so m f o r example, f y arranging c o l ots, wireless o tocols can b e s , i.e., the to p a rent MAC p p rotocols, to m l ogy graph h a u ted manne r , ] . Obviously, unfit for M A g y which is c o ntrary, the t o o cols are full y y be p romisi n N ET. topolog y -tra n ss link or no d i ng. a nsparent no d m binatorial d e r y in Galois fi e s [9], balanc e WS N ee of y * China sign. To ge t r , we aim t o n dant slot o f d throughput . n t slots wer e o ts, squashe s t ter through - n y topology - a ximal trans - m e given tim e f or a networ k o lliding trans - collision ca n e further ca t e - p olog y -depen - p rotocols. Fo r m inimize wire - a s to be set u p or in the sin k t he topology - A NET becaus e c aused by th e o polog y -trans - y independen t n g choices fo r n sparent MA C d e. In this pa - d e schedulin g e signs [5], in - fi eld [6,7], or - e d incomplet e N t o f . e s - - - e k - n - - r - p k - e e - t r C - g - - e 802 C. N. XU Copyright © 2010 SciRes. WSN block [10,11] and superimposed code[12-14]. The aim of them is same, that is, to give birth to a cover-free set as MAC scheduling codes, which is the key to QoS guaran- tee. Of course, the sets generated by different strategies are distinct even if they are feed with same parameters. Due to the existence of co mbinatorial designs, the car- dinal of the cover-free set is no less than the node num- ber of network [5 ]. Therefore, the prob lem of how to se- lect an appropriate subset comes into being, for every no- de has to be uniquely associated with one element of the cover-free set. In other word, if the node number of a network is N, and the cardinal of the set is M, then there are M N optional subsets which can be assigned as the MAC schedu ling tr agedy o f networ k. Obv iously, rando m selection is not a considerate policy, although it is ado- pted by all of the topology-transparent MAC scheduling protocols nowadays. Which subset can provide the best throughput gu aran tee? Fur ther, can the selected subset be optimized further? This paper tries to answer the ques- tions. We propose the definition of the redundant slot of the cover-free set, and pro ve that the redundant slot has neg- ative influence on thr oughpu t guaran tee. Furth er, we pro- ve that any subset of a cover-free set is still a cover-free set after any of its redundant slots is squashed out. There- fore, the more minimal throughput and the less maximal delay can be guaranteed. Our algorithm therefore picks the subset which has the maximal number of redundant slots, squashes all redundant slots of the subset, and then designates it as node scheduling strategy of network. Therefore, for any topology-transparent node scheduling strategy, both the increased minimal throughput and de- creased maximal transmission delay can be gotten by just using our algorithm as an extra accessory. 2. Network Model Wireless network is modeled by a directed graph G = (V, E), where V is the set of nodes and E is the set of directed links. If node w is within the transmission range of node u, then a directed edge connecting these two nodes is denoted by (u, w)E, with u being a neighbor of w. Th e degree of a node w, i.e.,()|{|(,) ,,}|DwuuwEuw V is defined as the number of its neighbors. We assume that the maximum nodal degree Dmax, i.e.,max( ) wVDw , remains constant when network operate s. O f course, Dmax > 0 is necessary for keeping connectivity. In this paper, we assume that the transmission channel is error-free and a reception failure is caused only by packet collisions. A packet transmitted from a neighbor of a node, is successfully received by the node only if no packet is transmitted from other neighbor nodes simul- taneously. All nodes are homogeneous. We also assume that the transceiver at each node is half-duplex. As a re- sult, a node cannot transmit and receive concurrently. Time is assumed to be synchronized over the network. Furthermore, time is slotted and slots are grouped into time frame. For example, a time frame consists of four time slots in Figure 1. In other word, a frame F = {S1, S2, …, Sb} consists of b consecutive slots. A slot assign- ment is given by a set ()Sw F for every node w, where S(w) consists of time slots in which node w has the transmitting right in a frame. 3. Redundant Slot and QoS Guarantee 3.1. Redundant Slot Definition 1. Assume [k] = {0, 1, …, k-1}, a set A = {A0, A1, …, AM-1} of subsets of the [T] is a (s, M, T) cover-free set if for any proper subset I of [M] su ch tha t |I| = s (|I| is the cardinal of set I), and any integer [] j MI , we have {} {} ji AA . s is called the intensity of the co- ver-free set. Cover-free set is equivalent with the d-disjunct matrix [15] and the superimposed code. A (s, M, T) cover-free set A can be represented by a T × M matrix A where 101,0 1 0 j ij j if iA AiTjM if iA The matrix is referred as the scheduling matrix. For convenience, the jth column vector and the ith row vec- tor of the scheduling matrix A are denoted as A*j and Ai* respectively. Besides, for a T × M scheduling matrix, ATj is the MSB (Most Significant Bit) of A*j and A0j is the LSB (Least Significant Bit) of A*j. Definition 2. For two vectors X = (x1, x2, …, xm)T and Y = (y1, y2, …, ym)T, the sum of X and Y is 112 2 (, ,...,) T mm XYx yxyxy . If X + Y = X, then Y is covered by X. Obviously, for the scheduling matrix of a (s, M, T) cover-free set, any column vector is not covered by any other s column vectors. Lemma 1. Any L ( s LM ) elements in a (s, M, T) Figure 1. An example of MAC scheduling code. C. N. XU 803 Copyright © 2010 SciRes. WSN cover-free set form a (s, L, T) cove r- free set. Proof: For the scheduling matrix of a (s, M, T) cov- er-free set, any one column vector will not be covered by any other s column vectors. So it will not be covered by any other L column vectors since L < s. Therefore, it is a (s, L, T) cover-free family. Definition 3. Assume the scheduling matrix of a (s, M, T) cover-free set is denoted as A, for some integer i (01iT ) and an y integer j(0 1)jM , if Aij = 0 or Aij = 1, then i is a redundant slot of A. Theorem 1. Assume the scheduling matrix of a (s, M, T) cover-free set is denoted as A, a (1)TM matrix which is generated by removing (deleting, or squashing) redundant slot of A is a (s, M, T-1) cover-free set. Proof: For any s + 1 column vectors of A, without loss of generality, assume them to be A*0, A*1, …, A*s. Ob- viously, A*s is not covered by A*0 + A*1 + … + A*(s-1) . In other word, there exist at least one integer k (01kT ), which satisfies [1] (1)({}{0}) ks ki is A Atrue . Therefore, k is not a redundant slot of A. Assume a (1)TM matrix B is generated by squashing any one redundant slot of A, and A*0, A*1, …, A*s are turned into B*0, B*1, …, B *s correspondingly. Since k is not a redundant slot of A, Ak* is still kept in B. Thus, B*s is not covered by B*0 + B*1 + … + B*(s-1). Con- sidering the generality of choosing A*0, A*1, …, and A*s, the set of all column vectors in B is a (s, M, T-1) cov- er-free set. Redundant slot results in less throughput guarantee. Assume the scheduling matrix of a (s, M, T) cover-free set to be A and i is one of its redundant slot. If 01 {}{0} ij jM A , none of nodes will transmit at slot i. On the other hand, if 01 {}{1} ij jM A , all nodes will transmit at slot i and no any packets can be received cor- rectly due to the half-duplex transceiver. In a word, the throughput of redundant slots is wasted in both cases. 3.2. Redundant Slot and QoS Guarantee Definition 4. The minimal guaranteed throughput Gmin is defined as the ratio of the number of guaranteed suc- cessful transmissions in one frame to frame length. Definition 5. The transmission delay under the worst traffic condition is called the maximal transmission de- lay, and it is defined as the ratio of frame length to the minimal number of successful transmission slots in one frame. Theorem 2. For a (s, M, T) cover-free set A and a (s, M, T-1) cover-free set A’ which is generated by squash- ing one redundant slot of A, if the minimal guaranteed throughput and the maximal transmission delay are Gmin and max DT , and ' min G and 'ma x D T respectively when A and A’ are adopted respectively as node scheduling codes, then' min min //(1)GG TT , and ' max max /(1)/DT DTTT . Proof: For any node, assume there are at least k exclu- sive transmission slots can be guaranteed if A is adop- ted as the MAC scheduling codes of network, based on the definition of the minimal guaranteed throughput, min k GT . Similarly, if A’ is adopted, ' min 1 k GT . Therefore, ' min min //(1)GG TT . Since the maximal transmission delay is the reciprocal of the minimal guaranteed throughput, ' max max /(1)/DT DTTT . 4. Algorithm and Performance Analysis 4.1. Algorithm For selecting N scheduling codes from M candidates, there are M N optional subsets in total. Based on Theorem 2, QoS guarantee can be enhanced if a redundant slot is squashed. So our algo rithm chooses the su bset which has the maximal number of redundant slots, squashes all re- dundant slots of the subset, and then designates it as the node scheduling strategy. 4.2. Performance Analysis Theorem 3. Assume the scheduling matrix of a (s, M, T) cover-free set to be ATM, if its row vectors have equal weight w, then the algorithm can squash at least i redun- dant slots if the node number N satisfies (1) M iwNMiw (01 M iw , and i is an integer). Proof: We prove it using mathematical induction. 1) If M wNM , i.e., i = 0, Theorem 3 is ob- viously correct. 2) Assume when (1) M kwNMkw , at least k redundant slots can be squashed. 3) If (2) (1) M kwNMkw , since (1) M kwNwMkw , for N + w nodes, at least k redundant slots can be squashed from ATM based on the assumption 2). If the scheduling matrix af- ter the k redundant slots are squashed from ATM is notated () ()( ) k TkNw A . Since the row weight of ATM is w, there are at most w column vectors whose MSBs are 1 in() ()( ) k TkNw A . In other word, there are at least N column vectors whose 804 C. N. XU Copyright © 2010 SciRes. WSN MSBs are 0 in() ()( ) k TkNw A . If we select any N column vectors whose MSBs are all 0 as the node scheduling codes of network, then the MSB slot is obviously a redundant slot. Therefore, at least k + 1 redundant slots can be founded and squashed. Corolla ry 1. Fo r the scheduling matrix A of a (s, M, T) cover-free set, if its row vectors have equal weight M-w, then if the node number N satisfies (1) M iwNMiw （01 M iw , and i is an integer） , the algorithm can squash at least i redundant slots. Proof: Since the scheduling matrix is just the com- plementary matrix of that in Theorem 3, the proof is ob- vious. 5. Apply into Popular Topology-Transparent Node Scheduling Strategies Based on Theorem 3, the performance of our algorithm can be estimated if the row vectors in scheduling matrix have equal weight. Therefore, to show its universality, we prove that the most popular topology-transparent no- de scheduling strategies generate scheduling matrix with equal weight. 5.1. Strategy Based on the Multinomial Theory in Galois Field Both Chlamtac’s and Ju’s algorithm are based on the multinomial theory in Galois field. Based on two input parameters, the node number N and the maximal node degree Dmax, two parameters q and k are get based on a sufficient condition of forming a cover-free set. Further, based on q and k, every node is associated with a unique vector (ak, ak-1, …, a0), where []( 0,1,...,) i aqi k . In other word, every node is associated with a unique mul- tinomial 1 110 ... kk kk axaxax a . To map from the multinomial to scheduling matrix, a frame is divided into q subframes and a subframe is fur- ther divided into q slots. Every node has transmission right only at one slot dur ing a subfr ame. For ex ample, for the subframe i, []iq, node which is associated with the vector (ak, ak-1, …, a0) has transmission right only at the 1 110 ((...) mod) kk kk aiaiaiaq th slot in the subframe i. Theorem 4. For scheduling matrix generated by strategy based on the multinomial theory in Galois field with parameters q and k, its row vectors have equal weight qk. Proof: Based on the principle of the algorithm, the weight of the jth row vector in scheduling matrix is the number of node which has transmission right at the jth slot. For the slot j in subframe i, it is the number of vec- tor (ak, ak-1, …, a0) which satisfies 1 110 (...)mod kk kk aiaiai aqj . Assume 1 11 ... kk kk aiaiaimq z ,01zq where m is an integer. For every z, there is a unique 0()modajzq which satisfies 1 110 (...)mod kk kk aiaiai aqj , i.e., a0 is determined by (ak, ak-1, …, a1). In other word, there are k independent variables in (ak, ak-1, …, a0). So, the number of (ak,ak-1,…,a0) which satisfies 1 110 (...)mod kk kk aiaiai aqj is qk, i.e., the row vectors of scheduling matrix have equal weight qk. 5.2. Strategy Based on the Orthogonal Array Definition 5. A OA(k, t, v) is a k tv matrix with en- tries from [v], 0kt , if for any k kv submatrix, each of its vk column vectors is unique. A OA(k, t, v) can be mapped into a k vt v schedul- ing matrix. A frame is composed of vt slots. Each node is assigned a unique column vector of orthogonal array as its scheduling code. For example, if a node is assigned a column vector (0, 3, 1), its scheduling code is 000110000010. Theorem 6. For scheduling matrix generated by stra- tegy based on OA(k, t, v), its row vectors have equal weight vk-1. Proof: For any k row vectors in OA(k, t, v), they form a k kv matrix. Since every column vector in the k kv matrix is unique, there are vk different k-tuples. Since every entry in [v] appears equal times in any row vector, every entry appears vk-1 times in any row vector. Based on the mapping from orthogonal array to schedul- ing matrix, every row vector of scheduling matrix has equal weight vk-1. 5.3. Strategy Based on Orthogonal Latin Square Definition 7. A orthogonal latin square with order p is a pp matrix, with every row and every column to be a full permutation of [p]. Definition 8. Two different nn latin squares A = (ai, j), B = (bi,j), ,{1,2,...,}ij n is orthogonal if all 2-tuples (ai,j, b i,j) are different. As a generalization, r nn latin squares A(1),A(2),…,A(r) form a latin squares family with order (r, n) if they are different and ortho- gonal between any two of them. Especially, if r = n-1, the latin squares family is a complete orthogonal latin squares family with order n. C. N. XU 805 Copyright © 2010 SciRes. WSN A complete orthogonal latin squares family with order n can be mapped into a 2(1)nnn scheduling matrix. For all n(n-1) column vectors in the family, each of them can be associated to a node as its scheduling code. Theorem 6. If n is a prime or prime power, for sche- duling matrix generated by strategy based on a complete orthogonal latin squares family with order n, its row vectors have equal weight n-1. Proof: Since a complete orthogonal latin squares fam- ily with order n consists of n-1 latin squares if n is a prime or prime power. For each latin square, every ele- ment appears just once in any column and row. So, the weight of the scheduling matrix is n-1 based on the map- ping from latin square to scheduling matrix. 6. Experiments We take the Chlamtac algorithm for examples to test the effect of the redundant slot squashing algorithm. Based on the principle of Chlamtac algorithm, given the node number N and the maximum nodal degree Dmax, the two parameters, q and k, can be get. For example, if N = 120，Dmax = 5, then q = 1 1，k = 2. That is, we have qk+1 = 1331 candidate node scheduling codes for 120 nodes. In fact, there are at least 11 redundant slots can be squashed. Figure 2 illustrates the relationship among qk+1/N, N and Dmax generated by Chlamtac algorithm. Obviously, the larger the qk+1/N is, the more redundant slots can be anticipated. Seen from Figure 2, qk+1/N increases quickly with N or Dmax. So it can be easily anticipated that our algorithm performs better in network with more nodes or larger no- de degree. We now begin to test the effect of our algorithm under various values of N and Dmax for Chlamtac algorithm. The range of N is 2~60, and that of the maximal node degree is 1~N-1, i.e., all possibilities of maximal node degree are tested. Figure 3 illustrates the effect of our algorith m. The th ree coordinates are the node number N, the maximal node degree Dmax and the number of redun- dant slot. It can be found from Figure 3 that ther e a lwa ys exist redundant slots in any case. The larger the N or Dmax is, the more redundant slots can be squashed, which is consistent with our anticipation. 7. Conclusions The topology-transparent node scheduling strategy is suit- able for MANET because it can provide guaranteed QoS and be independent of network topology. In this paper, to improve QoS guarantee, we present a universal algo- rithm which can be realized as an accessory of any to- pology-tran s pa re nt n ode scheduling strategy nowaday s. Figure 2. The relationship among qk+1/N, N and Dmax gener- ated by the Chlmatac algorithm. Figure 3. The effect of redundant slot squashing algorithm for the Chlamtac algorithm. Node scheduling codes generated by each topology- transparent node scheduling algorithm nowadays form a cover-free set. We propose the redundant slot of the cov- er-free set, and prove that the redundant slot has negative influence on the minimal guaranteed throughput. Further, we prove that any subset of a cover-free set is still a cov- er-free set after any of its redundant slots is squashed. Our algorithm chooses the subset which has the maximal number of redundant slots, squashes all redundant slots of the subset, and then designates it as the node schedul- ing strategy of wireless network. Both theoretical analy- sis and experiments prove that the increased minimal throughput and decreased maximal transmission delay are guaranteed. Simulation results reveal that the larger the network node number or the maximal node degree, the better QoS can be guaranteed by employing our algorithm. 8. References [1] X. Lin and N. Shroff, “The Impact of Imperfect Schedul- ing on Cross-layer Congestion Control in Wireless Net- works,” IEEE/ACM Transactions on Networking, Vol. 14, 806 C. N. XU Copyright © 2010 SciRes. WSN No. 2, 2006, pp. 302-315. [2] R. Nelson and L. Kleinrock, “Spatial TDMA - A Colli- sion-Free Multihop Channel Access Protocol,” IEEE Tran- sactions on Communications. Vol. 33, No. 9, 1985, pp. 934-944. [3] T. Moscibroda, R. Wattenhofer and Y. Weber, “Protocol Design Beyond Graph-based Models,” Proceedings of the ACM 5th Workshop Hot Topics in Networks, Pisa, 2006, pp. 25-30. [4] A. Behzad and I. Rubin, “On the Performance of Graph- Based Scheduling Algorithms for Packet Radio Networks,” Proceedings of the IEEE Global Telecommunications Co n- ference, San Francisco, 2003, pp. 3432-3436. [5] A. Shen, “Combinatorial Theory,” Shanghai Jiao Tong Uni- versity Press, Shanghai, 2008. [6] I. Chlamtac and A. Farago, “Making Transmission Sche- dules Immune to Topology Changes in Multi-Hop Packet Radio Networks,” IEEE/ACM Transactions on Network- ing, Vol. 2, No. 1, 1994, pp. 23-29. [7] J. Ju and V. O. K. Li, “An Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 6, No. 3, 1998, pp. 298-306. [8] V. R. Syrotiuk, C. J. Colbourn and A. C. H. Ling, “To- pology-Transparent Scheduling for MANETs Using Or- thogonal Arrays,” Proceedings of the 9th Annual Interna- tional Conference on Mobile Computing and Networking, San Diego, 2003, pp. 43-49. [9] J. Ju and V. O. K. Li, “TDMA Scheduling Design of Multihop Packet Radio Networks Based on Latin Squares,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, 1999, pp. 1345-1352. [10] B. Xiang and Y. M. Mao, “Balanced Incomplete Block Designs Based Scheduling Scheme for Multi-Hop Ad Hoc Networks,” Proceedings of IEEE International Con- ference on Communications, Circuits and Systems, Xia- men, 2008, pp. 388-393. [11] A. Dey, “Theory of Block Designs,” John Wiley & Sons, New York, 1986. [12] P. C. Li, G. H. J. Van Rees and R. Wei, “Constructions of 2-Cover-Fee Families and Related Separating Hash Fam- ilies,” Journal of Combinatorial Designs, Vol. 14, No. 6, 2006, pp. 423-440. [13] H. K. Kim and V. Lebedev, “On Optimal Superimposed Codes,” Journal of Combinatorial Designs, Vol. 12, No. 2, 2004, pp. 79-91. [14] W. H. Kautz and R. C. Singleton, “Nonrandom Binary Superimposed Codes,” IEEE Transaction on Information Theory, Vol. 10, No. 4, pp. 363-377, 1964. [15] P. Erdos, P. Frankl and Z. C. Furedi, “Families of Finite Sets in Which No Set is Covered by the Union of R Oth- ers,” Israel Journal of Mathematics, Vol. 51, No. 1-2, 1985, pp. 79-89. |