Many modern communication networks suffer significantly from the unreliable characteristic of their nodes and links. To deal with failures, traditionally, centralized erasure codes have been extensively used to improve reliability by introducing data redundancy. In this thesis, we address several issues in implementing erasure codes in a decentralized way such that coding operations are spread to multiple nodes. Our solutions are based on fountain codes and randomized network coding, because of their capability of being amenable to decentralized implementation originated from their simplicity and randomization properties. Our contributions consist of four parts. First, we propose a novel decentralized implementation of fountain codes utilizing random walks. Our solution does not require node location information and enjoys a small local routing table with a size in proportion to the number of neighbors. Second, we introduce priority random linear codes to achieve partial data recovery by partition and encoding data into non-overlapping or overlapping subsets. Third, we present geometric random linear codes to decrease communication costs in decoding significantly, by introducing modest data redundancy in a hierarchical fashion. Finally, we study the application of network coding in disruption tolerant networks. We show that network coding achieves shorter data transmission time than replication, especially when data buffers are limited. We also propose an efficient variant of network coding based protocol, which attains similar transmission delay, but with much lower transmission costs, as compared to a protocol based on epidemic routing.

Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2007-09-27 21:48:20.594 / Wireless networks are less reliable than wired networks because channels are “exposed” to the surrounding environment that is susceptible to interference and noise. To minimize losses of data due to collisions, wireless networks need a mechanism to regulate the access on the transmission medium. Medium Access Control (MAC) protocols control access to the shared communication medium so that it can be used efficiently. In this thesis, we first describe the collision-controlled Dual Prohibition Multiple Access (DPMA) protocol [45]. The main mechanisms implemented in DPMA, such as binary dual prohibition, power control, interference control, and support for differentiated services (DiffServ), are presented in detail. We conducted a thorough simulation study on DPMA protocol from several aspects. First, we conduct simulations to observe the effects of binary competition number (BCN), unit slot length and safe margin on the performance of DPMA. Secondly, the DiffServ capability of DPMA is demonstrated through simulation results. Finally, we compare the DPMA protocol with the CSMA/CA protocol and find that DPMA with optimal configuration has better performance than CSMA/CA under both low and high network density. / Master

During the route discovery process, each node receiving the route request packet (RReq) will retransmit it exactly once. A distant neighbor may accidentally receive/loose the only RReq and use it to announce a new route, although that link is inferior/superior for route reply packets (RRep) or actual message routing. Overall, the constructed route may be far from the optimal. All existing route discovery schemes (including DSR/AODV) apply retransmission during route discovery exactly once (1R). Based on a realistic physical layer model, we propose two new route discovery schemes: n-retransmission (nR, retransmitting exactly n times) and n-retransmission c-reception (ncRR), retransmitting until we either reach a total of n own retransmissions or c copies from neighbors are heard. We compare our two new scheme with the traditional one, under otherwise identical conditions (same metric, same packet reception probability on each link) and the same choices about possibly retransmitting again upon discovering a better route (R+) or discarding it (R1), generating route reply packet for every received RRep (B*), or for first and better discovered routes only (B2), and retransmitting RRep exactly once (A1), up to a maximum of three times (A3), or optimally u times decided by link quality (Au). Experimental results show that the proposed ncRR scheme (for n=2 and c=3 or c=4) achieves the best tradeoff between quality of route, success rate and message overhead in the route discovery process, followed by the nR scheme, and both of them are superior to the existing traditional schemes.

This thesis presents several simple, robust, and optimal resource management schemes for multihop wireless access networks with the main focus on multi-channel wireless mesh networks (MC WMNs). In this regard, various resource management optimization problems are formulated arid efficient algorithms are proposed to solve each problem. First, we consider the channel as signment problem in MC-WMNs and formulate different resource management problems within the general framework of network utility maximization (NUM). Unlike most of the previously proposed channel assignment schemes, our algorithms can not only assign the orthogonal (i.e., non-overlapped) channels, but also partially overlapped channels. This better utilizes the avail able frequency spectrum as a critical resource in MC-WMNs. Second, we propose two distributed random medium access control (MAC) algorithms to solve a non-convex NUM problem at the MAC layer. The first algorithm is fast, optimal, and robust to message loss and delay. It also only requires a limited message passing among the wireless nodes. Using distributed learning techniques, we then propose another NUM-based MAC algorithm which achieves the optimal performance without frequent message exchange. Third, based on our results on random MAC, we develop a distributed multi-interface multi-channel random access algorithm to solve the NUM problem in MC-WMNs. Different from most of the previous channel assignment schemes in the literature, where channel assignment is intuitively modeled in the form of combinatorial and discrete optimization problems, our scheme is based on formulating a novel continuous optimization model. This makes the analysis and implementation significantly easier. Finally, we consider the problem of pricing and monetary exchange in multi-hop wireless access networks, where each intermediate node receives a payment to compensate for its offered packet forwarding service. In this regard, we propose a market-based wireless access network model with two-fold pricing. It uses relay-pricing to encourage collaboration among the access points. It also uses interference pricing to leverage optimal resource management. In general, this thesis widely benefits from several mathematical techniques as both modeling and solution tools to achieve simple, robust, optimal, and practical resource management strategies for future wireless access networks.

With the constant expansion of the industrial monitoring system, there is an urgent requirement to reduce investment and operating costs for the development of industrial communication technology. For industrial real-time monitoring systems, wireless technology can be used in a practical industrial production to take advantages of its flexibility and robustness. As wireless sensor networks have many advantages such as low investment costs, flexible structure and ease of transformation, it has become the focus with regards to industrial areas. THVRG is a routing algorithm that selects the routing path based on two-hop information. Since different information sensed by the sensors may have different requirements in order to reach the sink, a priority-based routing algorithm is required in order to adapt to this kind of situation. This thesis has proposed a priority routing algorithm based on the THVRG (Priority-based THVRG). In addition, a simulation of this algorithm was performed in OPNET. Finally, the report provides an evaluation of the proposed algorithm in industrial wireless sensor networks.

Multi-hop wireless network are promising techniques in the field of wireless communication. The dynamic topology of the network and the independent selfish participants of the network make it difficult to be modeled by traditional tools. Game theory is one of the most powerful tools for such problems. However, most current works have certain limitations. There has not been widely accepted solution for the problem yet. In this thesis we propose our solutions for the problem of bandwidth sharing in wireless networks. We assume the nodes are rational, selfish but not malicious independent agents in the game. In our model, nodes are trying to send their data to the access point. Some nodes may require others to forward their package to successfully connect to the access point. However, nodes are selfish and do not wish to help others. Therefore it is possible that some nodes may refuse the requirement. In that case, the unpleasant nodes may punish the others by slowing down their traffic, in which case both parties will suffer. Therefore it is non-trivial to find out the Equilibrium for these nodes after the bargain process. What is the proper distribution of resources among these nodes? We propose a solution based on the game theory. Our solution fulfils the goal of fairness and social welfare maximum.

Scheduling in wireless networks plays an important role. The undeterministic nature of the wireless channel is usually considered as an undesirable property. Recently, the idea of opportunistic scheduling is introduced and it takes advantage of the time-varying channel for performance improvement such as throughput and delay. Since the introduction of opportunistic scheduling, there are two main bodies of works. The first body of works assume that each user is greedy and has infinite backlog for transfer. With this assumption, fairness objective becomes an important factor in designing a scheduling algorithm to avoid severe starvation of certain users. Typical fairness involve processor sharing time fairness, proportional fairness, and minimum performance guarantee. On the other hand, delay performance is not a appropriate factor to evaluate the effectiveness of a scheduling algorithm because of the infinite backlog assumption. In reality, this assumption is not true as data arrives and leaves the network randomly in practice. The second body of works deal with the relaxation of the infinite backlog assumption. Thus, the notion of stability region arises. The definition of stability is that the queue at each source node remains finite. Stability region can be defined as the set of traffic intensities which can all be stabilized by the network. The well known throughput optimal algorithm is proven capable of achieving the largest stability region. In this thesis, two innovative opportunistic scheduling algorithms which aim to minimize the amount of resources used to stabilize the current traffics are proposed. The key feature of our algorithm is that the incoming traffic rates are available to the scheduler, whereas the throughput optimal algorithm has no such prior traffic knowledge. Performance comparisons are made by means of simulation to demonstrate that the proposed algorithms can achieve the same stability region as the throughput optimal algorithm. Moreover, the delay performance is better than that of the throughput optimal algorithm, especially under heavy traffic conditions.

In this thesis, we propose a scheduling problem for the downlink of a single cell system with multiple sectors. We formulate an optimization problem based on a generalized round robin scheme that aims at minimizing the cycle length necessary to provide one timeslot to each user, while avoiding harmful interference. Since this problem is under-constrained and might have multiple solutions, we propose a second optimization problem for which we try to find a scheduling that minimizes the cycle length while being as efficient as possible in resource utilization. Both of these problems are large integer programming problems that can be solved numerically using a commercial solver, but for real time use, efficient heuristics need to be developed. We design heuristics for these two problems and validate them by comparing their performances to the optimal solutions.

Cooperative communication has recently re-emerged as a possible paradigm shift to realize the promises of the ever increasing wireless communication market; how- ever, there have been few, if any, studies to translate theoretical results into feasi- ble schemes with their particular practical challenges. The multiple-input multiple- output (MIMO) technique is another method that has been recently employed in different standards and protocols, often as an optional scenario, to further improve the reliability and data rate of different wireless communication applications. In this work, we look into possible methods and algorithms for combining these two tech- niques to take advantage of the benefits of both. In this thesis, we will consider methods that consider the limitations of practical solutions, which, to the best of our knowledge, are the first time to be considered in this context. We will present complexity reduction techniques for MIMO systems in cooperative systems. Furthermore, we will present architectures for flexible and configurable MIMO detectors. These architectures could support a range of data rates, modulation orders and numbers of antennas, and therefore, are crucial in the different nodes of cooperative systems. The breadth-first search employed in our realization presents a large opportunity to exploit the parallelism of the FPGA in order to achieve high data rates. Algorithmic modifications to address potential sequential bottlenecks in the traditional bread-first search-based SD are highlighted in the thesis. We will present a novel Cooperative Partial Detection (CPD) approach in MIMO relay channels, where instead of applying the conventional full detection in the relay, the relay performs a partial detection and forwards the detected parts of the message to the destination. We will demonstrate how this approach leads to controlling the complexity in the relay and helping it choose how much it is willing to cooperate based on its available resources. We will discuss the complexity implications of this method, and more importantly, present hardware verification and over-the-air experimentation of CPD using the Wireless Open-access Research Platform (WARP). / NSF grants EIA-0321266, CCF-0541363, CNS-0551692, CNS-0619767, EECS-0925942, and CNS-0923479, Nokia, Xilinx, Nokia Siemens Networks, Texas Instruments, and Azimuth Systems.

Wireless Sensor Network (WSN), a collection of “sensor nodes” promises to change the scientist’s approach of gathering the environmental data in various fields. Sensor nodes can be used for non-stop sensing, event detection, location sensing and local control of actuators, this concept gives surety to many latest application areas like agriculture, military, home or factory automation, logistics and so on. Remote surveillance and measurement missions can be performed by using WSNs. The hot research topic now-a-days is to make such networks remotely controllable and adaptive to the environment and mission. The work carried out in this thesis is the development of a surveillance application using TinyOS/nesC. The purpose of this application is to perform event-detection mission by using any one of the built-in sensor on Mica2 motes as well as a setup protocol is designed to make the WSN remotely controllable and adaptive to the mission. In this thesis, an experimental work is also performed using TinyDB to build up a surveillance system whose purpose is to detect and count the total number of person present at any time in a given room and to view the results at a remote place. Besides these two system applications, a comparative study between TinyDB and nesC is described which concludes that more hardware control can be achieved through nesC which is a more power efficient platform for long-term applications.