Commercial providers are increasingly permitting third-party developers to write and implement their own software applications on wireless devices, ranging from sensors to 3G cellular phones. As the number of applications and users grow, reliable software dissemination is quickly emerging as a key enabling technology, providing fundamental reprogramming services, such as software download, updates and security patching.
Intellectual Merit This project aims to develop analytical foundations for efficient software dissemination in loss-prone wireless networks, measured in terms of delay and communication/computational speed. Planned research will proceed along four thrusts: 1) PERFORMANCE LIMITS: mathematically formalizing the problem of software dissemination in multi-hop wireless networks using stochastic shortest path optimization based on the theory of Markov Decision Processes; 2) LARGE-SCALE ASYMPTOTICS: analyzing performance at high node densities using extreme-value theory and comparing state-of-the-art technologies, including rateless coding, packet-level channel hopping, and physical-layer cooperation; 3) ACK-LESS PROTOCOLS: eliminating control traffic (e.g., ACKnowledgments), with high probability, using a combination of extreme-value theory and shifted rateless codes; 4) IMPLEMENTATION: implementing theoretically-based software dissemination protocols on sensor motes and, subsequently, on Android-capable smartphones.
Broader Impact
This work promises a broad impact to various societal needs. On an education level, open cell phone programming expertise will be incorporated into innovative class assignments and labs taught by the PIs, including Software Engineering, Algorithms, and Networking. On a commercial side, the research identifies and provides directions for fundamental issues that will face private enterprises attempting to capitalize on emerging smartphone capabilities. The PIs will also expedite research transfer through liaisons with local and international industrial partners. Finally, the project will establish theoretical connections between disconnected fields, most notably bringing tools primarily used in civil and financial engineering into computing and communication.
The development of exciting and innovative software applications (apps) has played a major role in fueling the spectacular growth of the smartphone market. The ability to disseminate this software to users is a key enabling technology, incorporating software downloads, updates and security patches. The results of this research promise to enhance user's experience by reducing wireless traffic usage and improving the reliability of smartphone platforms and other emerging devices forming the Internet of Things. Intellectual Merit: This project established fundamental theoretical foundations for reliable software dissemination (and more generally data dissemination) in loss-prone wireless environments, wherein packet losses occur due to communication errors or collisions. We developed solutions that provide theoretical guarantees on performance while simultaneously lending themselves to practical implementation in real-world networks. Our work consisted of 1) theoretical analyses of the problem, based on the theories of Markov decision processes and rare events (extreme value theory); 2) protocol design, based on a new technology called rateless coding; and 3) simulation and actual implementation of the protocols on sensors and smartphones. This project advanced the state-of-the-art in the field of wireless communications and networking, in several ways: Traditionally, networks with high node density (as found within cities or at sporting events, for example) have confounded the design and operation of networking protocols. Leveraging analyses from extreme-value theory, we showed, counter-intuitively, that it is possible to design simple reliable broadcasting protocols precisely for these environments. Indeed, the benefits of rateless coding are magnified at high node density. Thus, our analytical results showed that rateless coding transmission over a single communication channel can be as efficient as plain transmission over an unlimited number of channels (assuming one radio transmitter per node). This project brought fundamental approaches to the design of dissemination protocols and demonstrated their effectiveness through implementation on real working prototypes (e.g., wireless sensors and smartphones). Broader Impact: This project contributed to the training of a dozen of graduate and undergraduate students involved with the research and testbed implementation. On the theory side, our graduate students performed cutting-edge research straddling the boundaries between several mathematics disciplines, specifically, 1) probability and statistics; 2) coding theory; 3) control; and 4) data structures and algorithms. Students involved in the testbed implementation learned to program sensor networks using TinyOS, making use of some of its most advanced modules (e.g. over-the-air programming). Students also learned to work with Android-based smartphones, giving them exposure to advanced programming interfaces for a high-impact product. The results of the research were published in prominent journals, and presented in various forums, including major conferences, foreign institutions, and industry. The research also entailed collaborations with foreign and industrial partners. Finally, the project faciliated the creation of an after-school course 'Computer Warriors' taught by one of the PIs to 3rd - 7th graders at a local elementary school.
