Max-Life Power Schedule for Connectivity and Biconnectivity in Wireless Ad Hoc Networks

Given the initial energy supplies and the maximal transmission power of the individual nodes in a wireless ad hoc network, a power schedule of duration t for a specified topological property is a scheduling of the transmission powers of the individual nodes over the period [0, t] such that (1) the total amount of energy consumed by each node during the period [0, t] does not exceed its initial energy supply, (2) the transmission power of each node at any moment in the period [0, t] does not exceed its maximal transmission power, and (3) the produced network topology at any moment in the period [0, t] satisfies the property . The problem Max-Life Power Schedule for seeks a power schedule of the maximal duration for . Let g be the golden ratio , and ε be an arbitrarily positive constant less than one. In this paper, we present a -approximation algorithm for Max-Life Power Schedule for Connectivity, a -approximation algorithm for Max-Life Power Schedule for 2-Node-Connectivity, and a -approximation algorithm for Max-Life Power Schedule for 2-Edge-Connectivity. This work is supported in part by Research Grants Council of Hong Kong under grant number CityU 9041040. Peng-Jun Wan received his Ph.D. degree from University of Minnesota, MS degree from The Chinese Academy of Science, and BS degree from Tsinghua University. He is currently an Associate Professor in Computer Science at Illinois Institute of Technology, and at City University of Hong Kong. His research interests include wireless networks, optical networks, and algorithm design and analysis. Chih-Wei Yi received his M.S. and B.S. degrees from National Taiwan University. He is currently a Ph.D. candidate at the Illinois Institute of Technology. His dissertational research focuses on wireless ad hoc networks. He is expected to graduate in 2005.     

Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks

We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method applies the Yao structure on the local Delaunay graph [1] in an ordering that are computed locally. This new structure has the following attractive properties: (1) it is a planar graph; (2) its node degree is bounded from above by a positive constant ; (3) it is a t-spanner (given any two nodes u and v, there is a path connecting them in the structure such that its length is no more than · C_del times of the shortest path in the unit disk graph); (4) it can be constructed locally and is easy to maintain when the nodes move around; (5) moreover, we show that the total communication cost is O(n log n) bits, where n is the number of wireless nodes, and the computation cost of each node is at most O(d log d), where d is its 2-hop neighbors in the original unit disk graph. Here C_del is the spanning ratio of the Delaunay triangulation, which is at most . And the adjustable parameter α satisfies 0 < α ≤ π/3. Yu Wang is an assistant professor in the Department of Computer Science, University of North Carolina at Charlotte. He received his Ph.D. degree in computer science from Illinois Institute of Technology in 2004, his B.S. degree and M.S. degree in computer science from Tsinghua University, China, in 1998 and 2000. His current research interests include computer networks, wireless networks, mobile computing, algorithm design, and artificial intelligence. His recent work focuses on designing power efficient algorithms for wireless ad hoc networks and sensor networks. He published more than 40 papers in peer-reviewed journals and conferences. He served as program committee member for sevaral conferences (such as IEEE INFOCOM, IEEE MASS, IEEE ICCCN, etc.). He also served as reviewers for a number of international journals and conferences. His paper titled "Sparse Power Efficient Topology for Wireless Networks" won a Best Paper Award from the 35th IEEE Hawaii International Conference on System Sciences in 2002. He is a member of the ACM, IEEE, and IEEE Communication Society. For more information, please see http://www.cs.uncc.edu/~ywang32. Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He received M.S. (2000) and Ph.D. (2001) degree at Department of Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Department of Computer Science and Bachelor degree at Department of Business Management from Tsinghua University, P.R. China in 1995. He is a member of the Chinese national team prepared for the International Mathematics Olympics (IMO) from 1988 to 1990. His research interests span the wireless ad hoc networks, game theory, computational geometry, and cryptography and network security. Recently, he focuses on performing research on the cooperation, energy efficiency, and distributed algorithms for wireless ad hoc and sensor networks. He has published about 60 conference papers in top-quality conferences such as ACM MobiCom, ACM MobiHoc, ACM SODA, ACM STOC, IEEE INFOCOM, etc. He has more than 30 journal papers published or accepted for publish. He is a Member of the ACM, IEEE, and IEEE Communication Society. Xiang Yang Liserved various positions (such as conference chair, local arrangement chair, financial chair, session chair, TPC member) at a number of international conferences such as IEEE INFOCOM, ACM MobiHoc, ACM STOC. Li recently also co-organized a special issue of ACM MONET on non-cooperative computing in wireless networks. For more information, please see http://www.cs.iit.edu/~xli.     

A Scheduling Framework for UWB & Cellular Networks

The max-min fair scheduling problem in wireless ad-hoc networks is a non-convex optimization problem. A general framework is presented for this optimization problem and analyzed to obtain a dual problem, which involves solving a series of optimization sub-problems. In the limit of infinite bandwidth ( ), the scheduling solution reduces to simultaneous transmission (spread spectrum) on all links (Negi and Rajeswaran, INFOCOM '04 (March 2004)). This motivates the analysis of the scheduling problem in the Ultra Wide Band (UWB) regime ( , but finite), a model for certain practical radios. A quadratic (in 1/W) lower bound to the single link capacity function is developed, which simplifies the dual sub-problem to a quadratic optimization (Negi and Rajeswaran, GLOBECOM '04, (Dec. 2004)). The solution to this sub-problem is then obtained under both total power and power spectral density constraints. This solution is utilized to iteratively construct the schedule (sub-band sizes) and power allocation, thus optimally solving the UWB max-min fair scheduling problem, to within any desired precision. Simulations on medium sized networks demonstrate the excellent performance of this scheme. A cellular architecture (not necessarily UWB) may also be considered in this framework. It is proved that Frequency Division Multiple Access is the optimal scheduling for a multi-band cellular architecture. This work was supported in part by the National Science Foundation under Career award 0347455. Arjunan Rajeswaran received his Masters degree in Electrical and Computer Engineering from Carnegie Mellon University in 2003. Since August 2003, he has been pursuing his doctoral research at Carnegie Mellon. His reserach interests lie in the area of wireless networks. His focus is in the application of information and communication theoretic tools towards wireless network design. Several IEEE publications reflect his curent research on Medium Access Control design and performance. Arjunan received the best student paper award at IEEE/ACM Broadnets 2004. Gyouhwan Kim received his B.S. and M.S. degree in Electronic Engineering from Sogang University in Korea, in 1994 and 1996, respectively. Since 1996, he has been working in the CDMA cellular system development team in Samsung Electronics. Currently, he is also working toward the Ph.D degree in the Department of Electrical and Computer Engineering at Carnegie Mellon University. His main research interests are in wireless networks and communication theory. Rohit Negi received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, India in 1995. He received the M.S. and Ph.D. degrees from Stanford University, CA, USA, in 1996 and 2000 respectively, both in Electrical Engineering. He has received the President of India Gold medal in 1995. Since 2000, he has been with the Electrical and Computer Engineering department at Carnegie Mellon University, Pittsburgh, PA, USA, where he is an Assistant Professor. His research interests include signal processing, coding for communications systems, information theory, networking, cross-layer optimization and sensor networks.     

Population Adaptation for Genetic Algorithm-based Cognitive Radios

Genetic algorithms are best suited for optimization problems involving large search spaces. The problem space encountered when optimizing the transmission parameters of an agile or cognitive radio for a given wireless environment and set of performance objectives can become prohibitively large due to the high number of parameters and their many possible values. Recent research has demonstrated that genetic algorithms are a viable implementation technique for cognitive radio engines. However, the time required for the genetic algorithms to come to a solution substantially increases as the system complexity grows. In this paper, we present a population adaptation technique for genetic algorithms that takes advantage of the information from previous cognition cycles in order to reduce the time required to reach an optimal decision. Our simulation results demonstrate that the amount of information from the previous cognition cycle can be determined from the environmental variation factor, which represents the amount of change in the environment parameters since the previous cognition cycle.

On the Scalability of 2-D Discrete Wavelet Transform Algorithms

The ability of a parallel algorithm to make efficient use of increasing computational resources is known as its scalability. In this paper, we develop four parallel algorithms for the 2-dimensional Discrete Wavelet Transform algorithm (2-D DWT), and derive their scalability properties on Mesh and Hypercube interconnection networks. We consider two versions of the 2-D DWT algorithm, known as the Standard (S) and Non-standard (NS) forms, mapped onto P processors under two data partitioning schemes, namely checkerboard (CP) and stripped (SP) partitioning. The two checkerboard partitioned algorithms (Non-standard form, NS-CP), and as (Standard form, S-CP); while on the store-and-forward-routed (SF-routed) Mesh and Hypercube they are scalable as (NS-CP), and as (S-CP), respectively, where M ² is the number of elements in the input matrix, and (0,1) is a parameter relating M to the number of desired octaves J as . On the CT-routed Hypercube, scalability of the NS-form algorithms shows similar behavior as on the CT-routed Mesh. The Standard form algorithm with stripped partitioning (S-SP) is scalable on the CT-routed Hypercube as M ² = (P ²), and it is unscalable on the CT-routed Mesh. Although asymptotically the stripped partitioned algorithm S-SP on the CT-routed Hypercube would appear to be inferior to its checkerboard counterpart S-CP, detailed analysis based on the proportionality constants of the isoefficiency function shows that S-SP is actually more efficient than S-CP over a realistic range of machine and problem sizes. A milder form of this result holds on the CT- and SF-routed Mesh, where S-SP would, asymptotically, appear to be altogether unscalable.     

Harnessing Traffic Uncertainties in Wireless Mesh Networks—A Stochastic Optimization Approach

In this paper, we investigate the routing optimization problem in wireless mesh networks. While existing works usually assume static and known traffic demand, we emphasize that the actual traffic is time-varying and difficult to measure. In light of this, we alternatively pursue a stochastic optimization framework where the expected network utility is maximized. For multi-path routing scenario, we propose a stochastic programming approach which requires no priori knowledge on the probabilistic distribution of the traffic. For the single-path routing counterpart, we develop a learning-based algorithm which provably converges to the global optimum solution asymptotically.

Analytical Study of TCP Performance over IEEE 802.11e WLANs

IEEE 802.11 Wireless LAN (WLAN) has become a prevailing solution for broadband wireless Internet access while the Transport Control Protocol (TCP) is the dominant transport-layer protocol in the Internet. Therefore, it is critical to have a good understanding of the TCP dynamics over WLANs. In this paper, we conduct rigorous and comprehensive modeling and analysis of the TCP performance over the emerging 802.11e WLANs, or more specifically, the 802.11e Enhanced Distributed Channel Access (EDCA) WLANs. We investigate the effects of minimum contention window sizes and transmission opportunity (TXOP) limits (of both the AP and stations) on the aggregate TCP throughput via analytical and simulation studies. We show that the best aggregate TCP throughput performance can be achieved via AP’s contention-free access for downlink packet transmissions and the TXOP mechanism. We also study the effects of some simplifying assumptions used in our analytical model, and simulation results show that our model is reasonably accurate, particularly, when the wireline delay is small and/or the packet loss rate is low.

A Low Complexity and Low Power SoC Design Architecture for Adaptive MAI Suppression in CDMA Systems

In this paper, we propose a reduced complexity and power efficient System-on-Chip (SoC) architecture for adaptive interference suppression in CDMA systems. The adaptive Parallel-Residue-Compensation architecture leads to significant performance gain over the conventional interference cancellation algorithms. The multi-code commonality is explored to avoid the direct Interference Cancellation (IC), which reduces the IC complexity from to . The physical meaning of the complete versus weighted IC is applied to clip the weights above a certain threshold so as to reduce the VLSI circuit activity rate. Novel scalable SoC architectures based on simple combinational logic are proposed to eliminate dedicated multipliers with at least saving in hardware resource. A Catapult C High Level Synthesis methodology is apply to explore the VLSI design space extensively and achieve at least speedup. Multi-stage Convergence-Masking-Vector combined with clock gating is proposed to reduce the VLSI dynamic power consumption by up to This paper was presented in part at IEEE ISCAS in Vancouver, Canada, May, 2004.     

On Sensor Network Reconfiguration for Downtime-Free System Migration

Many state-of-the-art wireless sensor networks have been equipped with reprogramming modules, e.g., those for software/firmware updates. System migration tasks such as software reprogramming, however, will interrupt normal sensing and data processing operations of a sensor node. Although such tasks are occasionally invoked, the long time of such tasks may disable the network from detecting critical events, posing a severe threat to many sensitive applications. In this paper, we present the first formal study on the problem of downtime-free migration. We demonstrate that the downtime can be effectively eliminated, by partitioning the sensors into subsets, and let them perform migration tasks successively with the rest still performing normal services. We then present a series of effective algorithms, and further extend our solution to a practical distributed and localized implementation. The performance of these algorithms have been evaluated through extensive simulations, and the results demonstrate that our algorithms achieve good balance between the sensing quality and system migration time.

Direct Digital Frequency Synthesis Based on a Two-Level Table-Lookup Scheme

In this work, a new direct digital frequency synthesizer (DDFS) is proposed, which is based on a new two-level table-lookup (TLTL) scheme combined with Taylor’s expansion. This method only needs a lookup-table size of total bits, one multiplier, one n × 3n/4-bit multiplier and two additional smaller multipliers, to generate both sine and cosine values (where n is the output precision). Compared with several notable DDFS’s, the new design has a smaller lookup-table size and higher SFDR (Spurious Free Dynamic Range) for high-precision output cases, at comparable multiplier and adder complexities. The DDFS is verified by FPGA and EDA tools using Synopsys Design Analyzer and UMC 0.25 μm cell library, assuming 16-bit output precision. The designed 16-bit DDFS has a small gate count of 2,797, and a high SFDR of 110 dBc.

---

     

A CMOS Monolithic Image-Reject Filter

A CMOS inductorless image-reject filter based on active RLC circuitry is discussed and designed with the emphasis on low-noise, low-power, and gigahertz-range circuits. Two -enhancement techniques are utilized to circumvent the low characteristics inherent in the simple feedback circuit. The frequency tuning is almost independent of tuning, facilitating the design of the automatic tuning circuitry. The stability and the tuning scheme of the filter are also discussed. Simulations using 0.6 m CMOS technology demonstrate the feasibility of the tunable image-reject filter for GSM wireless applications. Simulation results show 4.75 dB voltage gain, 9.5 dB noise figure, and –20 dBm IIP3 at a passband centered at 947 MHz. The image signal suppression is 60 dB at 1089 MHz and the power consumption is 27 mW.     

Effect of off-orientation of seed crystal on silicon carbide (SiC) single-crystal growth on the (11 $$\bar 2$$ 0) surface0) surface

The effect of off-orientation growth has been investigated in terms of stacking fault formation during physical vapor transport (PVT) growth of silicon carbide (SiC) single crystals on the (11 0) seed crystal surface. Occurrence of stacking fault formation is largely dependent on the direction of off-orientation, and basal plane stacking fault density is significantly reduced by growing the crystals on a (11 0) seed crystal off-oriented toward 〈0001〉. The density of the basal plane stacking faults rapidly decreases from 100–150 cm⁻¹ to ∼10 cm⁻¹ as the degree of off-orientation is increased from 0 to 10 deg. The results are interpreted in the framework of microscopic facet formation during PVT growth, and the introduction of off-orientation of seed crystal is assumed to prevent (01 0) and (10 0) microfacet formation on the (11 0) growing surface through modification of the surface growth kinetics and to suppress the stacking fault formation. An erratum to this article is available at .     

Finite-Memory Systems

Let K be a field, k and n positive integers and let matrices with coefficients in K. For any function

Conservative Input–State–Output Systems with Evolution on a Multidimensional Integer Lattice

A fundamental object of study in both operator theory and system theory is a discrete-time conservative system (variously also referred to as a unitary system or unitary colligation). In this paper we introduce three equivalent multidimensional analogues of a unitary system where the time axis , d>1, is multidimensional. These multidimensional formalisms are associated with the names of Roesser, Fornasini and Marchesini, and Kalyuzhniy–Verbovetzky. We indicate explicitly how these three formalisms generate the same behaviors. In addition, we show how the initial-value problem (including the possibility of initial conditions at infinity) can be solved for such systems with respect to an arbitrary shift-invariant sublattice as the analogue of the positive-time axis. Some of our results are new even for the d=1 case.First online version published in May 2005*The authors were supported in part by a grant from the US-Israel Binational Science Foundation.     

Channel Access Scheme for MIMO-Enabled Ad Hoc Networks with Adaptive Diversity/Multiplexing Gains

Transmission power control (TPC) is used in wireless networks to improve channel reuse and/or reduce energy consumption. It has been often applied to single-input single-output (SISO) systems, where each node is equipped with a single antenna. Multi-input multi-output (MIMO) systems can improve the throughput or the signal-to-noise ratio (SNR) by providing multiplexing or diversity gains, respectively. In this paper, we incorporate a power-controlled MAC protocol for a wireless network with two antennas per node. Our protocol, coined CMAC, combines different types of MIMO gains, allowing for dynamic switching between diversity and multiplexing modes so as to maximize a utility function that depends on both energy consumption and throughput. CMAC adapts the “antenna mode,” the transmission power, and the modulation order on a per-packet basis. By “antenna mode” we mean one of five possible transmit/receive antenna configurations: 1 × 1 (SISO), 2 × 1 (MISO-D), 1 × 2 (SIMO-D), 2 × 2 (MIMO-D), and 2 × 2 (MIMO-M). The second, third, and fourth configurations offer a diversity gain, whereas the last configuration offers a multiplexing gain. By using control packets to bound the transmission power of potentially interfering terminals, CMAC allows for multiple interference-limited transmissions to take place in the vicinity of a receiving terminal. We study via simulations the performance of CMAC in ad hoc topologies. Our results indicate that relative to non-adaptive protocols, CMAC achieves a significant improvement in both the overall energy consumption and the throughput.

Primality Proving via One Round in ECPP and One Iteration in AKS

In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time (heuristic time ). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve Primality Proving algorithm (ECPP) runs in random heuristic time (some variant has heuristic time complexity ) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density ) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density ( ) of primes whose primality can be proved in time complexity . For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily proved prime, thus we achieve heuristic time complexity for all primes.     

Planar defects and double-domain epitaxy in epitaxial YSi<Subscript>2−x</Subscript> and ErSi<Subscript>2−x</Subscript> thin films on Si substrates

Interfacial reactions of Y and Er thin films on both (111)Si and (001)Si have been studied by transmission electron microscopy (TEM). Epitaxial rare-earth (RE) silicide films were grown on (111)Si. Planar defects, identified to be stacking faults on planes with 1/6 displacement vectors, were formed as a result of the coalescence of epitaxial silicide islands. Double-domain epitaxy was found to form in RE silicides on (001)Si samples resulting from a large lattice mismatch along one direction and symmetry conditions at the silicide/(001)Si interfaces. The orientation relationships are [0001]RESi_2−x// Si, RESi_2−x//(001)Si and [0001]RESi_2−x/ Si, RESi_2−x//(001)Si. The density of staking faults in (111) samples and the domain size in (001) samples were found to decrease and increase with annealing temperature, respectively.     

A Symbolic Circuit Analysis-Oriented Algorithm for Finding a Common Tree of the Current and Voltage Graphs

A fundamental problem of symbolic analysis of electric networks when using the signal-flow (SFG) graph method is to find the common tree of the current and voltage graph ( and , respectively). In this paper we introduce a novel method in order to determine a common tree of both graphs, which may be used to obtain the symbolic network transfer function when carrying out the small-signal analysis of linear(ised) circuits.     

The Design of a 2-V 900-MHz CMOS Bandpass Amplifier

A 900 MHz low-power CMOS bandpassamplifier suitable for the applications of RFfront-end in wireless communication receiversis proposed and analyzed. In this design, thetemperature compensation circuit is used tostabilize the amplifier gain so that theoverall amplifier has a good temperaturestability. Moreover, the compact tunablepositive-feedback circuit is connected to theintegrated spiral inductor to generate thenegative resistance and enhance its value. The simple diode varactor circuit isadopted for center-frequency tuning. These twoimproved circuits can reduce the powerdissipation of the amplifier. An experimentalchip fabricated by 0.5 mdouble-poly-double-metal CMOS technologyoccupies a chip area of ; chip area. The measuredresults have verified the performance of thefabricated CMOS bandpass amplifier. Under a2-V supply voltage, the measured quality factoris tunable between 4.5 and 50 and the tunablefrequency range is between 845 MHz and 915 MHz. At , the measured is 20 dB whereas thenoise figure is 5.2 dB in the passband. Thegain variation is less than 4 dB in the rangeof 0–80^°C. The dc powerdissipation is 35 mW. Suitable amplifier gain,low power dissipation, and good temperaturestability make the proposed bandpass amplifierquite feasible in RF front-endapplications.     

A VLSI Architecture of the Square Root Algorithm for V-BLAST Detection

MIMO has been proposed as an extension to 3G and Wireless LANs. As an implementation scheme of MIMO systems, V-BLAST is suitable for the applications with very high data rates. The square root algorithm for V-BLAST detection is attractive to hardware implementations due to its low computational complexity and numerical stability. In this paper, the fixed-point implementation of the square root algorithm is analyzed, and a low complexity VLSI architecture is proposed. The proposed architecture is scalable for various configurations, and implemented for a 4 × 4 QPSK V-BLAST system in a 0.35 m CMOS technology. The chip core covers 9 and 190 K gates. The detection throughput of the chip depends on the received symbol packet length. When the packet length is larger than or equal to 100 bytes, it can achieve a maximal detection throughput of 128 160 Mb/s at a maximal clock frequency of 80 MHz. The core power consumption, measured at 2.7 V and room temperature, is about 608 mW for 160 Mb/s data rate at 80 MHz, and 81 mW for 20 Mb/s at 10 MHz. The proposed architecture is shown to meet the requirements for emerging MIMO applications, such as 3G HSDPA and IEEE 802.11n.