A Virtual-Queue based Backpressure Scheduling Algorithm for Heterogeneous Multi-Hop Wireless Networks

( Zhenzhen Jiao ),( Baoxian Zhang ),( Jun Zheng ) 한국인터넷정보학회 2015 KSII Transactions on Internet and Information Syst Vol.9 No.12

Backpressure based scheduling has been considered as a promising technique for improving the throughput of a wide range of communication networks. However, this scheduling technique has not been well studied for heterogeneous wireless networks. In this paper, we propose a virtual-queue based backpressure scheduling (VQB) algorithm for heterogeneous multi-hop wireless networks. The VQB algorithm introduces a simple virtual queue for each flow at a node for backpressure scheduling, whose length depends on the cache size of the node. When calculating flow weights and making scheduling decisions, the length of a virtual queue is used instead of the length of a real queue. We theoretically prove that VQB is throughput-optimal. Simulation results show that the VQB algorithm significantly outperforms a classical backpressure scheduling algorithm in heterogeneous multi-hop wireless networks in terms of the packet delivery ratio, packet delivery time, and average sum of the queue lengths of all nodes per timeslot.

R3: A Lightweight Reactive Ring based Routing Protocol for Wireless Sensor Networks with Mobile Sinks

( Sheng Yu ),( Baoxian Zhang ),( Zheng Yao ),( Cheng Li ) 한국인터넷정보학회 2016 KSII Transactions on Internet and Information Syst Vol.10 No.12

Designing efficient routing protocols for a wireless sensor network with mobile sinks (mWSN) is a challenging task since the network topology and data paths change frequently as sink nodes move. In this paper, we design a novel lightweight reactive ring based routing protocol called R3, which removes the need of proactively maintaining data paths to mobile sinks as they move in the network. To achieve high packet delivery ratio and low transmission cost, R3 combines ring based forwarding and trail based forwarding together. To support efficient ring based forwarding, we build a ring based structure for a network in a way such that each node in the network can easily obtain its ring ID and virtual angle information. For this purpose, we artificially create a virtual hole in the central area of the network and accordingly find a shortest cycled path enclosing the hole, which serves as base ring and is used for generating the remaining ring based structure. We accordingly present the detailed design description for R3, which only requires each node to keep very limited routing information. We derive the communication overhead by ring based forwarding. Extensive simulation results show that R3 can achieve high routing performance as compared with existing work.

An Energy Efficient Localized Topology Control Algorithm for Wireless Multihop Networks

Dezhong Shang,Baoxian Zhang,Zheng Yao,Cheng Li 한국통신학회 2014 Journal of communications and networks Vol.16 No.4

Localized topology control is attractive for obtaining reducednetwork graphs with desirable features such as sparser connectivityand reduced transmit powers. In this paper, we focus onstudying how to prolong network lifetime in the context of localizedtopology control for wireless multi-hop networks. For this purpose,we propose an energy efficient localized topology control algorithm. In our algorithm, each node is required to maintain its one-hopneighborhood topology. In order to achieve long network lifetime,we introduce a new metric for characterizing the energy criticalitystatus of each link in the network. Each node independentlybuilds a local energy-efficient spanning tree for finding a reducedneighbor set while maximally avoiding using energy-critical linksin its neighborhood for the local spanning tree construction. Wepresent the detailed design description of our algorithm. The computationalcomplexity of the proposed algorithm is deduced to beO(mlog n), where m and n represent the number of links andnodes in a node’s one-hop neighborhood, respectively. Simulationresults show that our algorithm significantly outperforms existingwork in terms of network lifetime.

R3: A Lightweight Reactive Ring based Routing Protocol for Wireless Sensor Networks with Mobile Sinks

Yu, Sheng,Zhang, Baoxian,Yao, Zheng,Li, Cheng Korean Society for Internet Information 2016 KSII Transactions on Internet and Information Syst Vol.10 No.12

Designing efficient routing protocols for a wireless sensor network with mobile sinks (mWSN) is a challenging task since the network topology and data paths change frequently as sink nodes move. In this paper, we design a novel lightweight reactive ring based routing protocol called R3, which removes the need of proactively maintaining data paths to mobile sinks as they move in the network. To achieve high packet delivery ratio and low transmission cost, R3 combines ring based forwarding and trail based forwarding together. To support efficient ring based forwarding, we build a ring based structure for a network in a way such that each node in the network can easily obtain its ring ID and virtual angle information. For this purpose, we artificially create a virtual hole in the central area of the network and accordingly find a shortest cycled path enclosing the hole, which serves as base ring and is used for generating the remaining ring based structure. We accordingly present the detailed design description for R3, which only requires each node to keep very limited routing information. We derive the communication overhead by ring based forwarding. Extensive simulation results show that R3 can achieve high routing performance as compared with existing work.

An Energy Efficient Localized Topology Control Algorithm for Wireless Multihop Networks

Shang, Dezhong,Zhang, Baoxian,Yao, Zheng,Li, Cheng The Korea Institute of Information and Commucation 2014 Journal of communications and networks Vol.16 No.4

Localized topology control is attractive for obtaining reduced network graphs with desirable features such as sparser connectivity and reduced transmit powers. In this paper, we focus on studying how to prolong network lifetime in the context of localized topology control for wireless multi-hop networks. For this purpose, we propose an energy efficient localized topology control algorithm. In our algorithm, each node is required to maintain its one-hop neighborhood topology. In order to achieve long network lifetime, we introduce a new metric for characterizing the energy criticality status of each link in the network. Each node independently builds a local energy-efficient spanning tree for finding a reduced neighbor set while maximally avoiding using energy-critical links in its neighborhood for the local spanning tree construction. We present the detailed design description of our algorithm. The computational complexity of the proposed algorithm is deduced to be O(mlog n), where m and n represent the number of links and nodes in a node's one-hop neighborhood, respectively. Simulation results show that our algorithm significantly outperforms existing work in terms of network lifetime.

DTN Routing with Back-Pressure based Replica Distribution

Jiao, Zhenzhen,Tian, Rui,Zhang, Baoxian,Li, Cheng The Korea Institute of Information and Commucation 2014 Journal of communications and networks Vol.16 No.4

Replication routing can greatly improve the data delivery performance by enabling multiple replicas of the same packet to be transmitted towards its destination simultaneously. It has been studied extensively recently and is now a widely accepted routing paradigm in delay tolerant networks (DTNs). However, in this field, the issue of how to maximize the utilization efficiency of limited replication quota in a resource-saving manner and therefore making replication routing to be more efficient in networks with limited resources has not received enough attention. In this paper, we propose a DTN routing protocol with back-pressure based replica distribution. Our protocol models the replica distribution problem from a resource allocation perspective and it utilizes the idea of back-pressure algorithm, which can be used for providing efficient network resource allocation for replication quota assignment among encountered nodes. Simulation results demonstrate that the proposed protocol significantly outperforms existing replication routing protocols in terms of packet delay and delivery ratio.

Utility Bounds of Joint Congestion and Medium Access Control for CSMA based Wireless Networks

( Tao Wang ),( Zheng Yao ),( Baoxian Zhang ),( Cheng Li ) 한국인터넷정보학회 2017 KSII Transactions on Internet and Information Syst Vol.11 No.1

In this paper, we study the problem of network utility maximization in a CSMA based multi-hop wireless network. Existing work in this aspect typically adopted continuous time Markov model for performance modelling, which fails to consider the channel conflict impact in actual CSMA networks. To maximize the utility of a CSMA based wireless network with channel conflict, in this paper, we first model its weighted network capacity (i.e., network capacity weighted by link queue length) and then propose a distributed link scheduling algorithm, called CSMA based Maximal-Weight Scheduling (C-MWS), to maximize the weighted network capacity. We derive the upper and lower bounds of network utility based on C-MWS. The derived bounds can help us to tune the C-MWS parameters for C-MWS to work in a distributed wireless network. Simulation results show that the joint optimization based on C-MWS can achieve near-optimal network utility when appropriate algorithm parameters are chosen and also show that the derived utility upper bound is very tight.

DTN Routing with Back-Pressure based Replica Distribution

Zhenzhen Jiao,Rui Tian,Baoxian Zhang,Cheng Li 한국통신학회 2014 Journal of communications and networks Vol.16 No.4

Replication routing can greatly improve the data deliveryperformance by enabling multiple replicas of the same packet tobe transmitted towards its destination simultaneously. It has beenstudied extensively recently and is now a widely accepted routingparadigm in delay tolerant networks (DTNs). However, in thisfield, the issue of how to maximize the utilization efficiency of limitedreplication quota in a resource-saving manner and thereforemaking replication routing to be more efficient in networks withlimited resources has not received enough attention. In this paper,we propose a DTN routing protocol with back-pressure basedreplica distribution. Our protocol models the replica distributionproblem from a resource allocation perspective and it utilizes theidea of back-pressure algorithm, which can be used for providingefficient network resource allocation for replication quota assignmentamong encountered nodes. Simulation results demonstratethat the proposed protocol significantly outperforms existing replicationrouting protocols in terms of packet delay and delivery ratio.

Measurement-based AP Deployment Mechanism for Fingerprint-based Indoor Location Systems

( Dong Li ),( Yan Yan ),( Baoxian Zhang ),( Cheng Li ),( Peng Xu ) 한국인터넷정보학회 2016 KSII Transactions on Internet and Information Syst Vol.10 No.4

Recently, deploying WiFi access points (APs) for facilitating indoor localization has attracted increasing attention. However, most existing mechanisms in this aspect are typically simulation based and further they did not consider how to jointly utilize pre-existing APs in target environment and newly deployed APs for achieving high localization performance. In this paper, we propose a measurement-based AP deployment mechanism (MAPD) for placing APs in target indoor environment for assisting fingerprint based indoor localization. In the mechanism design, MAPD takes full consideration of pre-existing APs to assist the selection of good candidate positions for deploying new APs. For this purpose, we first choose a number of candidate positions with low location accuracy on a radio map calibrated using the pre-existing APs and then use over-deployment and on-site measurement to determine the actual positions for AP deployment. MAPD uses minimal mean location error and progressive greedy search for actual AP position selection. Experimental results demonstrate that MAPD can largely reduce the localization error as compared with existing work.