Search

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop ([v.sub.i], [v.sub.j]), communication is effective only when [v.sub.i] is transmitting, [v.sub.j] is receiving, and no other node in proximity of [v.sub.j] is also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use are-decompositions of the complete [lambda]-fold directed graph [[??].sub.n] into directed complete bipartite subgraphs [[??].sub.a,b] as a model for ternary scheduling in WSNs. We associate the vertices of [[??].sub.n] with the nodes of the WSN, and occurrences of [[??].sub.a,b]s (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of [lambda][[??].sub.n] guarantees that every ordered pair of nodes in the WSN can communicate in A time slots. Index Terms--Direct combinatorial constructions, ternary schedules, wireless sensor networks.

We formulate a combinatorial model of impulse radio sequence (IRSs) to study sequence or signal design for ultra-wideband (UWB) radio with unmodulated time hopping Using this combinatorial model for IRSs, we develop necessary and sufficient conditions for the existence of IRSs. Several novel constructions for IRSs with optimal correlation properties are given. The constructions involve the Welch construction for Costas arrays, a quadratic polynomial construction over finite fields, recursive techniques for optical orthogonal codes, and combinatorial design techniques using perfect Mendelsohn designs (PMDs). Index Terms--Costas arrays, optical orthogonal codes, perfect Mendelsohn designs (PMDs), ultra-wideband (UWB) radios.

Covering arrays are combinatorial objects that have been successfully applied in design of test suites for testing systems such as software, hardware, and networks where failures can be caused by the interaction between their parameters. Let n and k be positive integers with k ≥ 3. Two vectors x ∈ ℤ g 1 n and y ∈ ℤ g 2 n are qualitatively independent if for any ordered pair (a , b) ∈ ℤ g 1 × ℤ g 2 , there exists an index j ∈ { 0 , 1 , ... , n − 1 } such that (x (j) , y (j)) = (a , b). Let G be a graph with k vertices v 1 , v 2 , ... , v k with respective vertex weights g 1 , g 2 , ... , g k . A mixed covering array on G , denoted by CA (n , G , ∏ i = 1 k g i) , is a k × n array such that row i corresponds to vertex v i , entries in row i are from Z g i ; and if { v x , v y } is an edge in G , then the rows x , y are qualitatively independent. The parameter n is the size of the array. Given a weighted graph G , a mixed covering array on G with minimum size is optimal. In this paper, we introduce some basic graph operations to provide constructions for optimal mixed covering arrays on the family of graphs with treewidth at most three. [ABSTRACT FROM AUTHOR]