File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Optimal data dissemination in stochastic and arbitrary wireless networks
Title  Optimal data dissemination in stochastic and arbitrary wireless networks 

Authors  
Advisors  
Issue Date  2012 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Abstract  Data dissemination among wireless devices is an essential application in wireless networks. In contrast to its wired counterparts which have more stable network settings, wireless networks are subject to network dynamics, such as variable network topology, channel availability and capacity, which are due to user mobility, signal collision, random channel fading and scattering, etc. Network dynamics complicate the protocol design for optimal data disseminations. Although the topic has been intensively discussed for many years, existing solutions are still not completely satisfactory, especially for stochastic or arbitrary networks. In this thesis, we address optimal data dissemination in both stochastic and arbitrary wireless networks, using techniques of Lyapunov optimization, graph theory, network coding, multiresolution coding and successive interference cancellation. We first discuss the maximization of timeaveraged throughput utility over a long run for unicast and multirate multicast, respectively, in stochastic wireless networks without probing into the future. For multisession unicast communications, a utilitymaximizing crosslayer design, composed of joint endtoend rate control, routing, and channel allocation, is proposed for cognitive radio networks with stochastic primary user occupations. Then, we study optimal multirate multicast to receivers with nonuniform receiving rates, also making dynamic crosslayer decisions, in a general wireless network with both a timevarying topology and random channel capacities, by utilizing random linear network coding and multiresolution coding. In both solutions, we assume users are selfish and prefer only to relay data for others with strong social ties. Such social selfishness of users is a new constraint in network protocol design. Its impact on efficient data dissemination in wireless networks is largely unstudied, especially under stochastic settings. Lyapunov optimization is applied in our protocol design achieving closetooptimal utilities. Next, we turn to latencyminimizing data aggregation in wireless sensor networks having arbitrary network topologies under the physical interference model. Different from our effort for stochastic networks where we target at timeaveraged optimality over a long run, the objective here is to minimize the timespan to accomplish one round of aggregation scheduling for all sensors in an arbitrary topology. This problem is NPhard, involving both aggregation tree construction and collisionfree link scheduling. The current literature mostly considers the protocol interference model, which has been shown to be less practical than the physical interference model in characterizing the interference relations in the real world. A distributed solution under the physical interference model is challenging since cumulative interferences from all concurrently transmitting devices need to be well measured. In this thesis, we present a distributed aggregation protocol with an improved approximation ratio as compared with previous work. We then discuss the tradeoff between aggregation latency and energy consumption for arbitrary topologies when the successive interference cancellation technique is in force. Another distributed algorithm is introduced with asymptotic optimality in both aggregation latency and latencyenergy tradeoff. Through theoretical analysis and empirical study, we rigorously examine the optimality of our protocols comparing with both the theoretical optima and existing solutions. 
Degree  Doctor of Philosophy 
Subject  Resource allocation. Wireless communication systems. Lyapunov functions. Graph theory. Coding theory. Radio  Interference. 
Dept/Program  Computer Science 
DC Field  Value  Language 

dc.contributor.advisor  Lau, FCM   
dc.contributor.advisor  Wu, C   
dc.contributor.author  Li, Hongxing   
dc.contributor.author  李宏兴   
dc.date.issued  2012   
dc.description.abstract  Data dissemination among wireless devices is an essential application in wireless networks. In contrast to its wired counterparts which have more stable network settings, wireless networks are subject to network dynamics, such as variable network topology, channel availability and capacity, which are due to user mobility, signal collision, random channel fading and scattering, etc. Network dynamics complicate the protocol design for optimal data disseminations. Although the topic has been intensively discussed for many years, existing solutions are still not completely satisfactory, especially for stochastic or arbitrary networks. In this thesis, we address optimal data dissemination in both stochastic and arbitrary wireless networks, using techniques of Lyapunov optimization, graph theory, network coding, multiresolution coding and successive interference cancellation. We first discuss the maximization of timeaveraged throughput utility over a long run for unicast and multirate multicast, respectively, in stochastic wireless networks without probing into the future. For multisession unicast communications, a utilitymaximizing crosslayer design, composed of joint endtoend rate control, routing, and channel allocation, is proposed for cognitive radio networks with stochastic primary user occupations. Then, we study optimal multirate multicast to receivers with nonuniform receiving rates, also making dynamic crosslayer decisions, in a general wireless network with both a timevarying topology and random channel capacities, by utilizing random linear network coding and multiresolution coding. In both solutions, we assume users are selfish and prefer only to relay data for others with strong social ties. Such social selfishness of users is a new constraint in network protocol design. Its impact on efficient data dissemination in wireless networks is largely unstudied, especially under stochastic settings. Lyapunov optimization is applied in our protocol design achieving closetooptimal utilities. Next, we turn to latencyminimizing data aggregation in wireless sensor networks having arbitrary network topologies under the physical interference model. Different from our effort for stochastic networks where we target at timeaveraged optimality over a long run, the objective here is to minimize the timespan to accomplish one round of aggregation scheduling for all sensors in an arbitrary topology. This problem is NPhard, involving both aggregation tree construction and collisionfree link scheduling. The current literature mostly considers the protocol interference model, which has been shown to be less practical than the physical interference model in characterizing the interference relations in the real world. A distributed solution under the physical interference model is challenging since cumulative interferences from all concurrently transmitting devices need to be well measured. In this thesis, we present a distributed aggregation protocol with an improved approximation ratio as compared with previous work. We then discuss the tradeoff between aggregation latency and energy consumption for arbitrary topologies when the successive interference cancellation technique is in force. Another distributed algorithm is introduced with asymptotic optimality in both aggregation latency and latencyenergy tradeoff. Through theoretical analysis and empirical study, we rigorously examine the optimality of our protocols comparing with both the theoretical optima and existing solutions.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.source.uri  http://hub.hku.hk/bib/B4832971X   
dc.subject.lcsh  Resource allocation.   
dc.subject.lcsh  Wireless communication systems.   
dc.subject.lcsh  Lyapunov functions.   
dc.subject.lcsh  Graph theory.   
dc.subject.lcsh  Coding theory.   
dc.subject.lcsh  Radio  Interference.   
dc.title  Optimal data dissemination in stochastic and arbitrary wireless networks   
dc.type  PG_Thesis   
dc.identifier.hkul  b4832971   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Computer Science   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b4832971   
dc.date.hkucongregation  2012   