Scheduling In Wireless Networks With Multiple Packet Reception

Wireless network is expected to use widely in both military and civil areas, such as military reconnaissance, battlefield communication, home networking, eHealth system, and environment monitoring and so on. In future, the scale of a wireless network and the density of smart devices connected by wireless communication will increase continuously. At the same time, a much higher communication quality is required to support diverse applications such as multimedia delivery. Today, however, the available wireless network technologies cannot meet the requirement for future applications in terms of performance, scalibility, etc.The capacity of moderm wireless communication system is interference-limited. In many wireless networks, the design imitates that in the wired counterpart. Basically, the wireless channel is modeled as a point-to-point channel based on the single packet reception. A receiver node attempts to detect only one packet even when there are multiple packets in the received signal. When the arrivals of multiple transmissions overlap, collision occurs and the reception fails.Due to the broadcast nature, a wireless channel is open, sharing and fragile in nature. Therefore, the capacity of the wireless channel cannot be fully used with the point-to-point abstraction. To achieve a higher network performance, one should go beyond the classic design principle, and build a wireless network according to the substaintial feature of a wireless channel.Multipacket reception (MPR) is a promising progress at the physical layer. When collision occurs, nowadays, the collided signal is usually discarded. In comparison, MPR strives to extract multiple packets from the composite signal. Basically, with MPR, the design of a wireless network aims not to avoid interference, but to encourage simultaneous transmission, i.e., embracing interference. It is a great breakthrough over the classic design based on signal packet reception. At this time, the open and sharing nature of a wireless channel is no longer injurious, but a favorable condition to support simultaneous transmission. Due to the pontential to improve the network performance, MPR is expected to use widely in future (e.g., in the 4G cellular networks).Though significant progress has been made in MPR techniques at the physical layer, little attention has been paid to the design of support protocols at high layers. As there are specific requirements to ensure the feasibility of an MPR method, it is necessary to coordinate the transmissions carefully to meet the requirements. During the reception procedure, the involved signals are not interfered with eath other, but dependent and closely correlated. The protocols for single packet reception do not take into account the signal correlation. Therefore, they are not suitable for a wireless network with MPR.We take successive interference cancellation (SIC) as an example of MPR to study TDMA (time division multiple access)-based link scheduling in a network with SIC.SIC is an effective way of MPR to resolve the transmission collision. With SIC, the receiver tries to detect multiple received signals using an iterative approach. In each iteration, the strongest signal is decoded, by treating the remaining signals as interference. If a required SINR (signal to interference and noise ratio) is satisfied, this signal can be decoded and removed from the received composite signal. In the subsequent iteration, the next strongest signal is decoded, and the process continues until either all the signals are decoded or a point is reached where an iteration fails.Link scheduling is a fundamental issue in wireless networking and received a lot of attention recently. In a wireless network, link scheduling mainly focuses on the allocation and access of a wireless channel among a number of links. By channel contention and allocation, a scheduling scheme can make use of the wireless channel efficiently and effectively as well as provide high per-user communication quality.In the literature, there are two major interference models: the protocol model and the physical model. The former models the network by characterizing the interference between any two links. The latter takes into account the interference accumulation effect, which means that, when there are multiple interfering signals, the overall interference is the sum of all of them.The content and novel results of this thesis are summarized into four parts.First, the study of link scheduling based on the protocol interference model in a network with SIC.We propose a simultaneity graph (SG) to capture the effect of SIC and define interference number to measure the interference of a link. We show that scheduling over SG is NP-hard and the maximum interference number bounds the performance of a maximal greedy scheme. An independent set based greedy scheme is explored to efficiently construct a maximal feasible schedule. Moreover, with careful selection of link ordering, we present a scheduling scheme that improves the bound.The performance is evaluated by both simulations and measurements in a testbed based on USRP. The throughput gain is on average 40% and up to 120% over IEEE 802.11. In most scenarios, the number of vertices in an SG is larger by a factor O(log2n) than that in a conflict graph, where n is the number of links in the netowrk.Second, the study of link scheduling based on the physical interference model in a network with SIC.Due to the accumulation effect and the sequential detection nature of SIC, the interference of a link cannot be accurately evaluated until the set of concurrent links (i.e., the context of the link) is known. We propose a weighted simultaneity graph (WSG) to characterize the interference based on the physical interference model when SIC is available. WSG is based on SG and employs weight to characterize the cumulative interference. As link scheduling based on WSG is NP-hard, we resort to a greedy algorithm to construct a near-optimal schedule. We propose a new type of greedy scheduling scheme, context-aware scheduling. And then, we define tolerance margin to measure the saturation of a link set and present two heuristic policies: one is to schedule the link to a slot such that the resulting set of links has a maximum tolerance margin; the other is to choose a slot such that the decrease of tolerance margin is minimum. Simulation results show that the proposed schemes outperform the well-known first-fit policy, e.g., a throughput gain between 20% and 60% is achieved.Third, we study the problem of maximizing the number of successful transmissions in the physical interference model in a wireless network with SIC.The aim is to choose a set of links as large as possible such that every intended receiver can successfully detect its desired signal when all links are active simultaneously. This problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. For example, in many link scheduling schemes, the overall schedule comprises several maximal feasible link sets.We first provide an accurate description of the problem by use of mathematical programming. Afterwards, we show that, the problem is NP-hard when SIC is applied. And then, we define transmission cost to measure the interference of a link set and propose an efficient greedy scheme accordingly. The approximation ratio is bounded by the transmission cost of the constructed link set. The time complexity of the newly proposed scheme is O(n4). We evaluate the proposed scheme by extensive simulations and show that it performs very well, e.g., the size of the link set is no less than 70% of the optimal one.Fourth, the study of scheduling performance and network transport capacity when SIC is available.In the experiments, though SIC is effective in improving the network performance, the improvement is less than the expectation from the previous theoretical studies. Therefore, we conduct an extensive analysis about scheduling performance and network capacity when SIC is available. Our findings include:Given a scheduling scheme that is unaware of SIC, the same order of the approximation ratio is achieved no matter whether or not SIC is available.Based on the protocol model, the capacity of a network with SIC is O( n ). Based on the physical model, when arbitrary transmission power is allowed, the capacity with SIC is O(n); otherwise, it is O(n(η-1/η)). In comparison to the capacity with single packet reception, when arbitrary transmission power is allowed, the capacity with SIC has a higher order; otherwise, the capacity is improved by SIC by a constant factor.In both the chain and cell network topologies, SIC improves the performance significantly, e.g., a gain between 20% and 200% is achieved by SIC. However, unless SIC is properly characterized, any scheduling scheme cannot effectively utilize the new transmission opportunities. Therefore, to accurately measure the performance of a scheduling scheme, in addition to the approximation ratio, new metrics are required to explicitly characterize the SIC capability.In summary, we study in depth link scheduling in a wireless network with SIC. We propose several new scheduling schemes with high performance and low overhead, and investigate the scheduling performance and network capacity of a wireless network with SIC. The results are important in both theory and practice, which can help us to understand the fundamental law of a wireless network with SIC. They can also promote the application of the MPR techniques such as SIC. The system model and technical solution in this thesis can serve as a guide and reference to the protocol design for other MPR methods.