A mobility-transparent deterministic broadcast mechanism for ad hocnetworks

Broadcast (distributing a message from a source node to all other nodes) is a fundamental problem in distributed computing. Several solutions for solving this problem in mobile wireless networks are available, in which mobility is dealt with either by the use of randomized retransmissions or, in the case of deterministic delivery protocols, by using conflict-free transmission schedules. Randomized solutions can be used only when unbounded delays can be tolerated. Deterministic conflict-free solutions require schedule recomputation when topology changes, thus becoming unstable when the topology rate of change exceeds the schedule recomputation rate. The deterministic broadcast protocols we introduce in this paper overcome the above limitations by using a novel mobility-transparent schedule, thus providing a delivery (time) guarantee without the need to recompute the schedules when topology changes. We show that the proposed protocol is simple and easy to implement, and that it is optimal in networks in which assumptions on the maximum number of the neighbors of a node can be made     

Controlled sink mobility for prolonging wireless sensor networks lifetime

This paper demonstrates the advantages of using controlled mobility in wireless sensor networks (WSNs) for increasing their lifetime, i.e., the period of time the network is able to provide its intended functionalities. More specifically, for WSNs that comprise a large number of statically placed sensor nodes transmitting data to a collection point (the sink), we show that by controlling the sink movements we can obtain remarkable lifetime improvements. In order to determine sink movements, we first define a Mixed Integer Linear Programming (MILP) analytical model whose solution determines those sink routes that maximize network lifetime. Our contribution expands further by defining the first heuristics for controlled sink movements that are fully distributed and localized. Our Greedy Maximum Residual Energy (GMRE) heuristic moves the sink from its current location to a new site as if drawn toward the area where nodes have the highest residual energy. We also introduce a simple distributed mobility scheme (Random Movement or RM) according to which the sink moves uncontrolled and randomly throughout the network. The different mobility schemes are compared through extensive ns2-based simulations in networks with different nodes deployment, data routing protocols, and constraints on the sink movements. In all considered scenarios, we observe that moving the sink always increases network lifetime. In particular, our experiments show that controlling the mobility of the sink leads to remarkable improvements, which are as high as sixfold compared to having the sink statically (and optimally) placed, and as high as twofold compared to uncontrolled mobility. Stefano Basagni holds a Ph.D. in electrical engineering from the University of Texas at Dallas (December 2001) and a Ph.D. in computer science from the University of Milano, Italy (May 1998). He received his B.Sc. degree in computer science from the University of Pisa, Italy, in 1991. Since Winter 2002 he is on faculty at the Department of Electrical and Computer Engineering at Northeastern University, in Boston, MA. From August 2000 to January 2002 he was professor of computer science at the Department of Computer Science of the Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas. Dr. Basagni’s current research interests concern research and implementation aspects of mobile networks and wireless communications systems, Bluetooth and sensor networking, definition and performance evaluation of network protocols and theoretical and practical aspects of distributed algorithms. Dr. Basagni has published over four dozens of referred technical papers and book chapters. He is also co-editor of two books. Dr. Basagni served as a guest editor of the special issue of the Journal on Special Topics in Mobile Networking and Applications (MONET) on Multipoint Communication in Wireless Mobile Networks, of the special issue on mobile ad hoc networks of the Wiley’s Interscience’s Wireless Communications & Mobile Networks journal, and of the Elsevier’s journal Algorithmica on algorithmic aspects of mobile computing and communications. Dr. Basagni serves as a member of the editorial board and of the technical program committee of ACM and IEEE journals and international conferences. He is a senior member of the ACM (including the ACM SIGMOBILE), senior member of the IEEE (Computer and Communication societies), and member of ASEE (American Society for Engineering Education). Alessio Carosi received the M.S. degree “summa cum laude” in Computer Science in 2004 from Rome University “La Sapienza.” He is currently a Ph.D. candidate in Computer Science at Rome University “La Sapienza.” His research interests include protocols for ad hoc and sensor networks, underwater systems and delay tolerant networking. Emanuel Melachrinoudis received the Ph.D. degree in industrial engineering and operations research from the University of Massachusetts, Amherst, MA. He is currently the Director of Industrial Engineering and Associate Chairman of the Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA. His research interests are in the areas of network optimization and multiple criteria optimization with applications to telecommunication networks, distribution networks, location and routing. He is a member of the Editorial Board of the International Journal of Operational Research. He has published in journals such as Management Science, Transportation Science, Networks, European Journal of Operational Research, Naval Research Logistics and IIE Transactions. Chiara Petrioli received the Laurea degree “summa cum laude” in computer science in 1993, and the Ph.D. degree in computer engineering in 1998, both from Rome University “La Sapienza,” Italy. She is currently Associate Professor with the Computer Science Department at Rome University “La Sapienza.” Her current work focuses on ad hoc and sensor networks, Delay Tolerant Networks, Personal Area Networks, Energy-conserving protocols, QoS in IP networks and Content Delivery Networks where she contributed around sixty papers published in prominent international journals and conferences. Prior to Rome University she was research associate at Politecnico di Milano and was working with the Italian Space agency (ASI) and Alenia Spazio. Dr. Petrioli was guest editor of the special issue on “Energy-conserving protocols in wireless Networks” of the ACM/Kluwer Journal on Special Topics in Mobile Networking and Applications (ACM MONET) and is associate editor of IEEE Transactions on Vehicular Technology, the ACM/Kluwer Wireless Networks journal, the Wiley InterScience Wireless Communications & Mobile Computing journal and the Elsevier Ad Hoc Networks journal. She has served in the organizing committee and technical program committee of several leading conferences in the area of networking and mobile computing including ACM Mobicom, ACM Mobihoc, IEEE ICC,IEEE Globecom. She is member of the steering committee of ACM Sensys and of the international conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous) and serves as member of the ACM SIGMOBILE executive committee. Dr. Petrioli was a Fulbright scholar. She is a senior member of IEEE and a member of ACM. Z. Maria Wang received her Bachelor degree in Electrical Engineering with the highest honor from Beijing Institute of Light Industry in China, her M.S. degree in Industrial Engineering/Operations Research from Dalhousie University, Canada and her Ph.D. in Industrial Engineering/Operations Research from Northeastern University, Boston. She served as a R&D Analyst for General Dynamics. Currently MS. Wang serves as an Optimization Analyst with Nomis Solutions, Inc.     

Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks

We define scalable models and distributed heuristics for the concurrent and coordinated movement of multiple sinks in a wireless sensor network, a case that presents significant challenges compared to the widely investigated case of a single mobile sink. Our objective is that of maximizing the network lifetime defined as the time from the start of network operations till the failure of the first node. We contribute to this problem providing three new results. We first define a linear program (LP) whose solution provides a provable upper bound on the maximum lifetime possible for any given number of sinks. We then develop a centralized heuristic that runs in polynomial time given the solution to the LP. We also define a deployable distributed heuristic for coordinating the motion of multiple sinks through the network. We demonstrate the performance of the proposed heuristics via ns2-based simulations. The observed results show that our distributed heuristic achieves network lifetimes that are remarkably close to the optimum ones, resulting also in significant improvements over the cases of deploying the sinks statically, of random sink mobility and of heuristics previously proposed for restricted sink movements.     

Finding a Maximal Weighted Independent Set in Wireless Networks

This paper introduces MWIS, a distributed algorithm for the efficient determination of a maximal weighted independent set in the topology graph G of a wireless network. Motivated by the observation that the problem of partitioning wireless nodes into clusters easily reduces to the problem of finding a maximal weighted independent set of nodes, the proposed algorithm is described by taking into account two main characteristics of wireless networks, namely, the broadcast nature of the wireless medium and the possibility to support nodes mobility. MWIS is executed at each node by means of fast message triggered procedures that require the sole knowledge of the topology local to the node. Moreover, its time complexity is proven to be bounded by a topology dependent parameter of the network (the stability number (G) of the network topology graph G), rather than by the invariant number n of the network nodes. Based on this result, and by using a well known result about (G) in the theory of random graphs the paper concludes with a brief discussion on the average time complexity of MWIS.     

Control of the Intermolecular Coupling of Dibromotetracene on Cu(110) by the Sequential Activation of CBr and CH Bonds

Dibromotetracene molecules are deposited on the Cu(110) surface at room temperature. The complex evolution of this system has been monitored at different temperatures (i.e., 298, 523, 673, and 723 K) by means of a variety of complementary techniques that range from STM and temperature‐programmed desorption (TPD) to high‐resolution X‐ray spectroscopy (XPS) and near‐edge X‐ray absorption fine structure spectroscopy (NEXAFS). State‐of‐the‐art density‐functional calculations were used to determine the chemical processes that take place on the surface. After deposition at room temperature, the organic molecules are transformed into organometallic monomers through debromination and carbon‐radical binding to copper adatoms. Organometallic dimers, trimers, or small oligomers, which present copper‐bridged molecules, are formed by increasing the temperature. Surprisingly, further heating to 673 K causes the formation of elongated chains along the Cu(110) close‐packed rows as a consequence of radical‐site migration to the thermodynamically more stable molecule heads. Finally, massive dehydrogenation occurs at the highest temperature followed by ring condensation to nanographenic patches. This study is a paradigmatic example of how intermolecular coupling can be modulated by the stepwise control of a simple parameter, such as temperature, through a sequence of domino reactions.     

Stereoselective Photopolymerization of Tetraphenylporphyrin Derivatives on Ag(110) at the Sub‐Monolayer Level

We explore a photochemical approach to achieve an ordered polymeric structure at the sub‐monolayer level on a metal substrate. In particular, a tetraphenylporphyrin derivative carrying para‐amino‐phenyl functional groups is used to obtain extended and highly ordered molecular wires on Ag(110). Scanning tunneling microscopy and density functional theory calculations reveal that porphyrin building blocks are joined through azo bridges, mainly as cis isomers. The observed highly stereoselective growth is the result of adsorbate/surface interactions, as indicated by X‐ray photoelectron spectroscopy. At variance with previous studies, we tailor the formation of long‐range ordered structures by the separate control of the surface molecular diffusion through sample heating, and of the reaction initiation through light absorption. This previously unreported approach shows that the photo‐induced covalent stabilization of self‐assembled molecular monolayers to obtain highly ordered surface covalent organic frameworks is viable by a careful choice of the precursors and reaction conditions.     

BlueMesh: Degree-Constrained Multi-Hop Scatternet Formation for Bluetooth Networks

In this paper we describe BlueMesh, a new protocol for the establishment of scatternets, i.e., multi-hop wireless networks of Bluetooth devices. BlueMesh defines rules for device discovery, piconet formation and piconet interconnection so to generate connected scatternets with the following desirable properties. BlueMesh forms scatternets without requiring the Bluetooth devices to be all in each other transmission range. BlueMesh scatternet topologies are meshes with multiple paths between any pair of nodes. BlueMesh piconets are made up of no more than 7 slaves. Simulation results in networks with over 200 nodes show that BlueMesh is effective in quickly generating a connected scatternet in which each node, on average, does not assume more than 2.4 roles. Moreover, the route length between any two nodes in the network is comparable to that of the shortest paths between the nodes.     

A logarithmic lower bound for time‐spread multiple‐access (TSMA) protocols

Time‐Spread Multiple‐Access (TSMA) protocols are scheduled access protocols for mobile multi‐hop radio networks that guarantee deterministic access to the shared channel regardless of the possibility of radio interference. In scheduled access methods, time is considered to be slotted and time slots are cyclically organized into frames. In general, the shorter the frame, the more efficient the protocol. An Ω(log log n) lower bound is known on the minimum length of the frame of TSMA protocols in networks with n nodes. In this note we improve that lower bound by characterizing the multiple access to the radio channel as a combinatorial problem. The proposed characterization allows us to prove that no TSMA protocols can successfully schedule the transmissions of the nodes of a multi‐hop radio network in frames with less than log n time slots. This revised version was published online in August 2006 with corrections to the Cover Date.