In Mobile Ad Hoc Networks (MANETs), nodes depend on each other for routing and forwarding packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and may not be willing to help other nodes. Such selfish behavior poses a real threat to the proper functioning of MANETs. One way to foster node cooperation is to introduce punishment for selfish nodes. Based on neighbor-monitoring techniques, a fully distributed solution to detect, punish, and re-admit selfish nodes, is proposed here. This solution provides nodes the same opportunity to serve/and be served by others. A light-weight solution regarding battery status is also proposed here. This solution requires neighbor monitoring only when necessary, thereby saving nodes battery power. Another effective way to solve the selfish-node problem is to reward nodes for their service according to their cost. To force nodes to show their true cost, truthful protocols are needed. A low overhead truthful routing protocol to find optimal routes is proposed in this thesis. The most prominent feature of this protocol is the reduction of overhead from existing solutions O(n3) to O(n2). A light-weight scalable truthful routing protocol (LSTOP) is further proposed, which finds near-least-cost paths in dense networks. LSTOP reduces overhead to O(n) on average, and O(n2) in worst case scenarios. Multiple path routing protocols are an effective alternative to single path routing protocols. A generic mechanism that can turn any table-driven multipath routing protocol into a truthful one, is outlined here. A truthful multipath routing protocol (TMRP), based on well-known AOMDV protocol, is presented as an example. TMRP incurs an only 2n message overhead for a route discovery, and can also achieve load balancing without compromising truthfulness. To cope with the selfish-node problem in the area of position-based routing, a truthful geographic forwarding (TGF) algorithm is presented. TGF utilizes three auction-based forwarding schemes to stimulate node cooperation. The truthfulness of these schemes is proven, and their performance is evaluated through statistical analysis and simulation studies.

The all-over trend for an universal access and ubiquitous access to the Internet is driving a revolution in our societies. In order to support this era of nomadic applications, new flexible network architectures have emerged. They are referred to as “wireless ad-hoc networks.” Since human-operated devices will more likely be used indoor, it leads to many issues related to the strength of the fading in this environment. Recently, it has been suggested that a possible interaction might exist between various parameters of the ad-hoc networks and, more precisely, between the propagation model and the routing protocol. To address this question, we present in this dissertation a cross-layer perspective of the analysis of these indoor ad-hoc networks. Our reasoning is made of four stages. First, the cross-layer interactions are analyzed by the means of multivariate statistical techniques. Since a cross-layering between the physical layer and the routing protocol has been proven to be significant, we further investigate the possible development a physical layer-constrained routing algorithm. Second, fundamental equations governing the wireless telecommunications systems are developed in order to provide insightful informations on how a reliable routing strategy should be implemented in a strongly-faded environment. After that, and in order to allow a better spatial reuse, the routing protocol we propose is further enhanced by the adjonction of a power control algorithm. This last feature is extensively analyzed and a closed-form expression of the link probability of outage in presence of non-homogeneous transmission powers is given. Numerous simulations corroborate the applicability and the performance of the derived protocol. Also, we evaluate the gain, in terms of radio channel ressources, that has been achieved by the means of the power control algorithm. Third, an architecture for the interconnection with a cellular network is investigated. A closed-form expression of the relaying stability of a node is given. This equation expresses the minimal requirement that a relaying node from the ad-hoc network must fullfil in order to bridge properly the connections to the base-station. Finally, a real-life implementation is provided as a validation of the applicability of this novel ad-hoc routing protocol. It is concluded that, both from the performance and the spatial re-use point-of-views, it can be taken advantage from the cross-layering between the physical and the routing layers to positively enhance the networking architectures deployed in an indoor environment.

Routing is the fundamental problem for Wireless Ad hoc networks, including Wireless Mobile Ad hoc networks (MANETs) and Wireless Sensor networks (WSNs). Although the problem has been extensively studied in the past decade, the existing solutions have deficiencies in one or more aspects including efficiency, scalability, robustness, complexity, etc.This dissertation proposes several new solutions for routing in WSNs and MANETs. Spiral is a data-centric routing algorithm for short-term communication in unstructured static WSNs. Spiral is a biased walk that visits nodes near the source before more distant nodes. This results in a spiral-like search path that is not only more likely to find a closer copy of the desired data than random walk, but is also able to compute a shorter route because the network around the source is more thoroughly explored. Compared with existing flooding and random walk approaches, Spiral has a lower search cost than flooding and returns better routes than random walk.Closest Neighbor First Search (CNFS) is a query processing algorithm for mobile wireless sensor networks. It is also walk-based and biased to visit nodes close to the source first. Different from Spiral, CNFS collects topology information as the search progresses. The topology information is used to compute the shortest return path for the query result and to tolerate the network topology changes caused by node mobility, which could otherwise cause the query to fail. CNFS requires fewer messages to process a query than flooding-based algorithms, while tolerating node mobility better than random walk-based algorithms.Address Aggregation-based Routing (AAR) is a novel routing protocol designed for MANETs. It reactively performs route discovery, but proactively maintains an index hierarchy called a Route Discovery DAG (RDD) to make route discovery efficient. The RDD contains aggregated node address information, requiring fewer packets for route discovery than the flooding used in existing protocols, while handling mobility better than pre-computing routes to all nodes. Compared with some existing popular protocols, AAR shows better performance in delivery rate, message overhead, latency and scalability.

This thesis presents the Forecasting Routing Technique (FORTEL), a routing protocol for Mobile Ad-Hoc Networks (MANETs) based on the nodes' Location Information. FORTEL stores the nodes' location information in the Location Table (LT) in order to construct routes between the source and the destination nodes. FORTEL follows the source routing strategy, which has rarely been applied in position-based routing. According to the source routing strategy, the end-to-end route is attached to the packet, therefore, the processing cost, in regards to the intermediate nodes that simply relay the packet according to route, is minimized. FORTEL's key mechanisms include: first, the location update scheme, employed to keep the LT entries up-to-date with the network topology. Besides the mobility variation and the constant rate location update schemes applied, a window location update scheme is presented to increase the LT's information accuracy. Second, the switching mechanism, between "Hello" message and location update employed, to reduce the protocol's routing overhead. Third and most important is the route computation mechanism, which is integrated with a topology forecasting technique to construct up-to-date routes between the communication peers, aiming to achieve high delivery rate and increase the protocol robustness against the nodes' movement. FORTEL demonstrates higher performance as compared to other MANET's routing protocols, and it delivers up to 20% more packets than AODV and up to 60 % more than DSR and OLSR, while maintaining low levels of routing overhead and network delay at the same time. The effectiveness of the window update scheme is also discussed, and it proves to increase FORTEL's delivery rate by up to 30% as compared to the other update schemes. A common and frequently occurring phenomenon, in wireless networks, is the Hidden Terminal problem that significantly impacts the communication performance and the efficiency of the routing and MAC protocols. Beaconless routing approach in MANETs, which delivers data packets without prior knowledge of any sort `of information, suffers from packet duplication caused by the hidden nodes during the contention process. Moreover, the throughput of the IEEE MAC protocol decreases dramatically when the hidden terminal problem occurs. RTS/CTS mechanism fails to eliminate the problem and can further degrade the network's performance by introducing additional overhead. To tackle these challenges, this thesis presents two techniques, the Sender Suppression Algorithm and the Location-Aided MAC, where both rely on the nodes' position to eliminate packet duplication in the beaconless routing and improve the performance of the 802.11 MAC respectively. Both schemes are based on the concept of grouping the nodes into zones and assign different time delay to each one. According to the Sender Suppression Algorithm, the sender's forwarding area is divided into three zones, therefore, the local timer, set to define the time that the receiver has to wait before responding to the sender's transmission, is added to the assigned zone delay. Following the first response, the sender interferes and suppresses the receivers with active timer of. On the other hand, the Location-Aided MAC, essentially a hybrid MAC, combines the concepts of time division and carrier sensing. The radio range of the wireless receiver is partitioned into four zones with different zone delays assigned to each zone. Channel access within the zone is purely controlled by CSMA/CA protocol, while it is time-based amongst zones. The effectiveness of the proposed techniques is demonstrated through simulation tests. Location-Aided MAC considerably improves the network's throughput compared to CSMA/CA and RTS/CTS. However, remarkable results come when the proposed technique and the RTS/CTS are combined, which achieves up to 20% more throughput as compared to the standalone RTS/CTS. Finally, the thesis presents a novel link lifetime estimation method for greedy forwarding to compute the link duration between two nodes. Based on a newly introduced Stability-Aware Greedy (SAG) scheme, the proposed method incorporates the destination node in the computation process and thus has a significant advantage over the conventional method, which only considers the information of the nodes composing the link.

Student Number : 0006936H - MSc research report - School of Electrical and Information Engineering - Faculty of Engineering and the Built Environment / Code division duplexing (CDD) has steadily garnered attention in the telecommunication community. In this project report we propose a physical layer implementation of CDD that utilizes orthogonal Gold codes as the means of differentiating transmission directions, in order to implement an ad-hoc networking infrastructure that is overlaid on a standard mobile networking topology, and hence creating a hybrid networking topology. The performance of the CDD based system is then comparatively assessed in two ways: from the perspective of the physical layer using point-to-point simulations and from the perspective of the network layer using an iterative snapshot based simulation where node elements are able to setup connections based on predefined rules.

However, applying directional antennas to wireless networks can also cause new collisions, such as the new hidden terminal problem and the deafness problem. We study the challenges in the MAC layer design with directional antennas and present the state of the art of current MAC protocols with directional antennas. Then, we propose a novel collision avoidance scheme in terms of BT-DMAC (Busy-Tone based Directional Medium Access Control) to address the new collisions with directional antennas. Both the analytical and simulation results show that transmitting busy tones on a different channel can effectively reduce the hidden nodes and mitigate the deafness problem. Thus, integrating multiple channels with directional antennas can bring numerous benefits. Furthermore, we also explore some techniques in the MAC layer design with directional antennas. Some useful insights are also given. / The capacity of wireless networks are mainly affected by two key factors: the interference among concurrent transmissions and the number of simultaneous transmissions on a single interface. Recent studies have found that, using multiple channels can separate concurrent transmissions and significantly improve network throughput. However, those studies only consider wireless nodes that are only equipped with omni-directional antennas, which cause high collisions. On the other hand, some researchers have found that directional antennas bring more benefits such as the reduced interference and the increased spatial reuse compared with omni-directional antennas. But, they only focused on a single-channel network which only allows finite concurrent transmissions. In this thesis, we propose a novel network architecture, in terms of multi-channel networks using multiple directional antennas ( MC-MDA), which integrates the two technologies of multiple channels and directional antennas together and potentially brings more benefits. / We study the capacity of MC-MDA networks and explore the benefits of such networks. We have found that using directional antennas in multi-channel networks can greatly increase the network capacity. Furthermore, such networks require fewer channels than multi-channels with omni-directional antennas. More specifically, we study the channel assignment problem of such MC-MDA networks. Our results indicate that using directional antennas in wireless networks can significantly reduce the required number of channels. Directional antennas have a better spectrum reuse than omni-directional antennas. / Dai, Hongning. / Adviser: Kam-Wing Ng. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3596. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 173-183). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Energy efficiency is crucial for ad hoc networks because of limited energy stored in the battery. Recharging the nodes frequently is sometimes not possible. Therefore, proper energy utilization is paramount. One possible solution of increasing energy efficiency is to optimize the transmitted packet size. But, we claim that only optimal packet size can not boost the energy efficiency in the noisy channel due to high packet loss rate and overhead. Hence, to reduce the overhead size and packet loss, compression and Forward Error Correction (FEC) code are used as remedy. However, every method has its own cost. For compression and FEC, the costs are computation energy cost and extra processing time. Therefore, to estimate the energy-optimize packet size with FEC or compression, processing energy cost and delay need to be considered for precise estimation. Otherwise, for delay sensitive real time applications (such as: VoIP, multimedia) over ad hoc network, energy efficient optimal packet size can be overestimated. We will investigate without degrading the Quality of Service (QoS) with these two different techniques FEC and compression, how much energy efficiency can be achieved by using the energy efficient optimal packet size for different scenarios such as: single hop, multi-hop, multiple source congested network etc. This thesis also shows the impact of time variable channel, packet fragmentation, packet collision on the optimal packet size and energy efficiency. Our results show that, for larger packets, error correction improves the energy efficiency in multi-hop networks only for delay tolerant applications. Whereas for smaller packets, compression is more energy efficient most of the cases. For real-time application like VoIP the scope of increasing the energy efficiency by optimizing packet after maintaining all the constraints is very limited. However, it is shown that, in many cases, optimal packet size improves energy efficiency significantly and also reduces the overall packet loss.

Multi-hop wireless networks have been widely considered as promising approaches to provide more convenient Internet access for their easy deployment, extended coverage, and low deployment cost. However, providing high-speed and reliable services in these networks is challenging due to the unreliable wireless links, broadcast nature of wireless transmissions, and frequent topology changes. On the other hand, network coding (NC) is a technique that could significantly improve the network throughput and the transmission reliability by allowing intermediate nodes to combine received packets. More recently proposed symbol level network coding (SLNC), which combines packets at smaller symbol scale, is a more powerful technique to mitigate the impact of lossy links and packet collisions in wireless networks. NC, especially SLNC, is thus a particular effective approach to providing higher data rate and better transmission reliability for applications such as mobile content distribution in multihop wireless networks. This dissertation focuses on exploiting NC in multihop wireless networks. We studied the unique features of NC and designed a suite of distributed and localized algorithms and protocols for content distribution networks using NC and SLNC. We also carried out a theoretical study on the network capacity and performance bounds achievable by SLNC in mobile wireless networks. We proposed CodeOn and CodePlay for popular content distribution and live multimedia streaming (LMS) in vehicular ad hoc networks (VANETs), respectively, where many important practical factors are taken into consideration, including vehicle distribution, mobility pattern, channel fading and packet collision. Specifically, CodeOn is a novel push based popular content distribution scheme based on SLNC, where contents are actively broadcast to vehicles from road side access points and further distributed among vehicles using a cooperative VANET. In order to fully enjoy the benefits of SLNC, we proposed a suite of techniques to maximize the downloading rate, including a prioritized and localized relay selection mechanism where the selection criteria is based on the usefulness of contents possessed by vehicles, and a lightweight medium access protocol that naturally exploits the abundant concurrent transmission opportunities. CodePlay is designed for LMS applicaitions in VANETs, which could fully take advantage of SLNC through a coordinated local push mechanism. Streaming contents are actively disseminated from dedicated sources to interested vehicles via local coordination of distributively selected relays, each of which will ensure smooth playback for vehicles nearby. CodeOn pursues a single objective of maximizing downloading rate, while CodePlay improves the performance of LMS service in terms of streaming rate, service delivery delay, and bandwidth efficiency simultaneously. CodeOn and CodePlay are among the first works that exploit the features of SLNC to simplify the protocol design whilst achieving better performance. We also developed an analytical framework to compute the expected achievable throughput of mobile content distribution in VANETs using SLNC. We presented a general analytical model for the expected achievable throughput of SLNC in a static wireless network based on flow network theory and queuing theory. Then we further developed the model to derive the expected achievable accumulated throughput of a vehicle driving through the area of interest under a mobility pattern. Our proposed framework captures the effects of multiple practical factors, including vehicle distribution and mobility pattern, channel fading and packet collision, and we characterized the impacts of those factors on the expected achievable throughput. The results from this research are not only of interest from theoretical perspective but also provide insights and guidelines on protocol design in SLNC-based networks.

Mobile Ad hoc networks (MANETs) are flexible networks that transmit packets node-by-node along a route connecting a given source and destination. Frequent link breaks (due to node mobility) and quick exhaustion of energy (due to limited battery capacity) are two major problems impacting on the flexibility of MANETs. Cooperative communication is a key concept for improving the system lifetime and robustness and has attracted considerable attention. As a result, there is much published research concerning how to utilize cooperative communication in a MANET context. In the past few years, most cooperative technologies have focused on lower layer enhancements, such as with the Physical Layer and MAC Layer, and have become very mature. At the Network Layer, although some research has been proposed, issues still remain such as the lack of a systematically designed cooperative routing scheme (including route discovery, route reply, route enhancement and cooperative data forwarding), the use of cooperative communication for mobility resilience, and route selection (jointly considering the energy consumption, energy harvesting potential and link break probability). Driven by the above concerns, a novel Constructive Relay based CooPerative Routing (CRCPR) protocol based on a cross-layer design is proposed in this thesis. In CRCPR, we fi rst modify the traditional hello message format to carry some additional neighbour information. Based on this information, a key aspect of this protocol is to construct one or more small rhombus topologies within the MANET structure, which are stored and maintained in a COoPerative (COP) Table and Relay Table. Next, the route request procedure is re-designed to improve resilience to node mobility with a scheme called Last hop Replacement. Finally, assuming nodes are mostly battery-powered, destination node based route-decision criteria are explored that can consider energy consumption, energy harvesting and link break probability to determine an appropriate route across the MANET. As the hello message format is modi ed to carry additional information, the control overhead is increased. However, in order to improve the control message eficiency, a new generalised hello message broadcasting scheme entitled Adjust Classi ed Hello Scheme is developed, which can be deployed onto every routing protocol employing a hello mechanism. As well as designing a new routing protocol for MANETs, including route discovery, route selection, route reply, route maintenance, route enhancement and cooperative data forwarding, the proposed scheme is implemented within an Opnetbased simulation environment and evaluated under a variety of realistic conditions. The results con rm that CRCPR improves mobility resilience, saves energy via cooperative communication and reduces the control overhead associated with the hello message mechanism.

Due to the broadcast nature of wireless medium, simultaneous transmissions interfere with each other (especially transmissions on nearby links), thus adversely affecting data rates and Quality of Service (QoS) in the system. Interference mitigation is therefore a fundamental issue that must be addressed in next generation wireless networks. An important technique for this is to control the links' transmission power. Driven by the wide spread of broadband wireless data services, a system-wide efficiency metric (i.e., system utility) is typically used to characterize the advantage of power control. / In interference-limited wireless networks where simultaneous transmissions on nearby links heavily interfere with each other, however, power control alone is not sufficient to eliminate strong levels of interference between close-by links. In this case, scheduling, which allows close-by links to take turns to be active, plays a crucial role for achieving high system performance. Joint power control and scheduling that maximizes the system utility has long been a challenging problem. The complicated coupling between the signal-to-interference ratio of concurrently active links as well as the flexibility to vary power allocation over time gives rise to a series of non-convex optimization problems, for which the global optimal solution is hard to obtain. The second goal of this thesis is to solve the non-convex joint power control and scheduling problems efficiently in a global optimal manner. In particular, it is the monotonicity rather than the convexity of the problem that we exploit to devise an efficient algorithm, referred to as S-MAPEL, to obtain the global optimal solution. To further reduce the complexity, we propose an accelerated algorithm, referred to as A-S-MAPEL, based on the inherent symmetry of the optimal solution. The optimal joint-power-control-and-scheduling solution obtained by the proposed algorithms serves as a useful benchmark for evaluating other existing schemes. With the help of this benchmark, we find that on-off scheduling is of much practical value in terms of system utility maximization if "off-the-shelf' wireless devices are to be used. / Maximizing a system-wide utility through power control is an NP-hard problem in general due to the complicated coupling interference between links. Thus, it is difficult to solve despite its paramount importance. The first goal of this thesis is to find global optimal power allocations to a variety of system utility maximization (SUM) problems based on the recent advances in monotonic optimization. Instead of tackling the non-convexity issue head on, we bypass non-convexity by exploiting the monotonic nature of the power control problem. In particular, we establish a monotonic optimization framework to maximize a system utility through power control in single-carrier or multi-carrier wireless networks. Furthermore, MAPEL and M-MAPEL are respectively proposed to obtain the global optimal power allocation efficiently in single-carrier or multi-carrier wireless networks. The main benefit of MAPEL and M-MAPEL is to provide an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL or M-MAPEL, we evaluate the performance of several existing algorithms through extensive simulations. On the other hand, by tuning the approximation factor in MAPEL and M-MAPEL, we could engineer a desirable tradeoff between optimality and convergence time. / With the proliferation of wireless infrastructureless networks such as ad hoc and sensor networks, it is increasingly crucial to devise an algorithm that solves the power control problem in a distributed fashion. In general, distributed power control is more complicated due to the lack of centralized infrastructure. As the third goal of this thesis, we consider a distributed power control algorithm for infrastructureless ad hoc wireless networks, where each link distributively and asynchronously updates its transmission power with limited message passing among links. This algorithm provably converges to the optimal strategy that picks global optimal solutions with probability 1 despite the non-convexity of the power control problem. In contrast with existing distributed power control algorithms, our algorithm makes no stringent assumptions on the system utility functions. In particular, the utility function is allowed to be concave or non-concave, differentiable or non-differentiable, continuous or discontinuous, and monotonic or non-monotonic. / Qian, Liping. / Adviser: Yingjun (Angela) Zhang. / Source: Dissertation Abstracts International, Volume: 72-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 133-139). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.