Includes bibliographical references (p. 45-47).

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

It has been envisioned that in the near future, wireless ad hoc networks would populate various application fields, ranging from disaster relief, environmental monitoring, surveillance, to medical applications, the observation of chemical and biological processes and community mesh networks. The decentralized and self-organizing nature of wireless ad hoc networks makes distributed algorithms fit very well in these networks, which however pose great challenges to the algorithm designers as they try to achieve optimal efficiency in communications. In this thesis, I develop a set of distributed algorithms addressing these challenges and solving some fundamental communication problems in wireless ad hoc networks. Communications in wireless ad hoc networks happen on a shared medium, and consequently are subject to interference. The first part of the thesis focuses on disseminating information on multiple-access channels while avoiding collisions. For both single-channel and multi-channel networks, the complexity of information dissemination is investigated, and nearly optimal distributed algorithms are proposed. The second part of the thesis focuses on designing efficient distributed algorithms for some fundamental problems under the physical Signal-to-Interference-plus-Noise-Ratio (SINR) interference model. The SINR model defines global fading interference with which the success of a signal reception depends on all simultaneous transmissions. Compared with graph based models, the SINR model reflects the fading and cumulative nature of radio signals. Hence, the SINR model represents the physical reality more precisely. However, the global nature of the SINR model makes the analysis of distributed algorithms much more challenging. Two types of fundamental problems are addressed in this part. The first type is closely related to communication coordination, including the wireless link scheduling problem and the node coloring problem. The second type of problems are about basic communication primitives, including the local broadcasting problem and the multiple-message broadcast problem. I investigate the complexity of these fundamental problems under the SINR interference model, and present efficient or optimal distributed algorithms. In the third part of the thesis, I propose a general interference model that can include commonly adopted interference models as special cases, and study whether efficient distributed algorithms can still be designed and analyzed in such a general model. Specifically, the affectance model is proposed in this part, which depicts the relative interference (affectance) on communication links caused by transmitting nodes. Both graph based models and the SINR model can be transformed into the affectance model. Under this general model, distributed algorithms with worst-case guarantees for the local broadcasting problem are presented. I also show how to make use of the developed techniques to get nearly optimal algorithms under the graph based model and the SINR model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

In scuba diving any problem that can be solved underwater will be solved underwater. This helps to prevent a dive from being disrupted. If a diver is separated from the group and is unable to find the group within a short time both the diver and dive group must surface to find each other and rejoin. To prevent the separation of divers a Stray Diver Alert System has been devised involving wireless communication to track the diver's position relative to the dive masters. Underwater communication holds many challenges that are not found in above water networks. Through simulation, it has been shown that the communication requirements for the Stray Diver Alert can be met with existing technology and protocols. This has been done by evaluating the resolution, power consumption and physical size of the device for three different communication protocols. This has shown that current technology is capable of meeting the requirements of the stray diver alert system.

Peer-to-peer (P2P) applications are enormously popular on the Internet. Their uses vary from file sharing to Voice-over-IP to gaming and more. Increasingly, users are moving toward wireless networked devices and wish to continue using P2P applications in these new environments. A mobile ad hoc network (MANET) is an infrastructureless network which allows users to dynamically form a mobile, wireless network. Though P2P and MANETs share some similarities, such as self-organization, dynamism, and resilience to failure, it is necessary to create new P2P algorithms that take advantage of the realities of MANETs. These algorithms must account for the numerous challenges found in these networks, including node mobility, resource constrained nodes, and the necessity of fully distributed algorithms. In this thesis, we propose a framework for mobile P2P computing in MANETs (P2P-MANETs). Our proposal includes the following components. First, nodes must be able to locate and join the P2P overlay. We therefore propose a fully distributed bootstrapping algorithm in which nodes multicast join requests and cache responses. Next, the overlay peers must form a topology of connections between themselves. We propose a fully distributed topology control heuristic which supports the dynamic nature of the P2P-MANET. It is important that peers contribute to the network by sharing their resources and forwarding traffic for others. We therefore propose a dynamically priced incentive scheme which rewards users for contributing to the network. We also propose a path selection algorithm to allow peers to select how many parts of a file to download from which servers and which paths to satisfy the user's preference for download time and cost. Finally, we propose a content distribution system that allows users to download large files through the use of network coding and multicasting. Each of these components is the first proposed for its respective place in a P2P-MANET architecture. Simulation results show that each of the proposed components achieves the goals set out for it and outperforms the comparison schemes. The results also show that the overlay topology and path selection heuristics provide good approximations compared to the optimal solutions. / Thesis (Ph.D, Computing) -- Queen's University, 2010-01-27 12:16:25.352

Mobile ad hoc networks (MANETs) eliminate the need for pre-existing infrastructure by relying on the nodes to perform all network services. The connectivity between the nodes is sporadic due to the shared, error-prone wireless medium and frequent route failures caused by node mobility. Fully self-organized MANETs are created solely by the end-users for a common purpose in an ad hoc fashion. Forming peer-to-peer security associations in MANETs is more challenging than in conventional networks due to the lack of central authority. This thesis is mainly concerned with peer- t o-peer key management in fully self-organized M ANETs. A key management protocol’s primary function is to bootstrap and maintain the security associations in the network, hence to create, distribute and revocate (symmetric or asymmetric) keying material as needed by the network security services. The fully self-organized feature means that t he key management protocol cannot rely on any form of off-line or on-line trusted third party (TTP). The first part of the thesis gives an introduction to MANETs and highlights MANETs' main characteristics and applications. The thesis follows with an overall perspective on the security issues in MANETs and motivates the importance of solving the key management problem in MANETs. The second part gives a comprehensive survey on the existing key management protocols in MANETs. The protocols are subdivided into groups based on their main characteristic or design strategy. Discussion and comments are provided on the strategy of each group. The discussions give insight into the state of the art and show researchers the way forward. The third part of the thesis proposes a novel peer- to-peer key management scheme for fully self-organized MANETs, called Self-Organized Peer-to-Peer Key Management (SelfOrgPKM). The scheme has low implementation complexity and provides self-organized mechanisms for certificate dissemination and key renewal without the need for any form of off-line or on-line authority. The fully distributed scheme is superior in communication and computational overhead with respect to its counterparts. All nodes send and receive the same number of messages and complete the same amount of computation. ScifOrgPKM therefore preserves the symmetric relationship between the nodes. Each node is its own authority domain which provides an adversary with no convenient point of attack. SelfOrgPKM solves t he classical routing-security interdependency problem and mitigates impersonation attacks by providing a strong one-to-one binding between a user’s certificate information and public key. The proposed scheme uses a novel certificate exchange mechanism t hat exploits user mobility but does not rely on mobility in anyway. The proposed certificate exchange mechanism is ideally suited for bootstraping the routing security. It enables nodes to setup security associations on the network layer in a localized fashion without any noticeable time delay. The thesis also introduces two generic cryptographic building blocks as the basis of SelfOrgPKM: 1) A variant on the ElGamal type signature scheme developed from the generalized ElGamal signature scheme introduced by Horster et al. The modified scheme is one of the most efficient ElGamal variants, outperforming most other variant s; and 2) A subordinate public key generation scheme. The thesis introduces t he novel notion of subordinate public keys, which allows the users of SelfOrgPKM to perform self-organized, self-certificate revocation without changing their network identifiers / addresses. Subordinate public keys therefore eliminate the main weakness of previous efforts to solve the address ownership problem in Mobile IPv6. Furthermore, the main weakness of previous efforts to break t he routing-security interdependence cycle in MANETs is also eliminated by a subordinate public key mechanism. The presented EIGamal signature variant is proved secure in t he Random Oracle and Generic Security Model (ROM+ GM ) without making any unrealistic assumptions . It is shown how the strong security of the signature scheme supports t he security of t he proposed subordinate key generation scheme. Based on the secure signature scheme a security argument for SelfOrgPKM is provided with respect to a genera l, active insider adversary model. The only operation of SelfOrgPKM affecting the network is the pairwise exchange of certificates. The cryptographic correctness, low implementation complexity and effectiveness of SelfOrgPKM were verified though extensive simulations using ns-2 and OpenSSL. Thorough analysis of the simulation results shows t hat t he localized certificate exchange mechanism on the network layer has negligible impact on network performance. The simulation results also correlate with efficiency analysis of SelfOrgPKM in an ideal network setting, hence assuming guaranteed connectivity. The simulation results furthermore demonstrate that network layer certificate exchanges can be triggered without extending routing protocol control packet. / Thesis (M.Sc.Eng.)-University of KwaZulu-Natal, Durban, 2005.

Nowadays, with a worldwide market penetration of over 50% in the mobile telecommunications sector, there is also an unrelenting demand from the subscribers for ever increasing transmission rates and availability of broadband-like experience on the handset. Due to this, research in next-generation networks is rife. Such systems are expected to achieve peak data rates of up to 1 Gbps through the use of innovative technologies such as multiple-input and multipleoutput (MIMO) and orthogonal frequency division multiple access (OFDMA). Two more ways of boosting capacity have also been identified: shrinking cell sizes and greater reuse of resources in the same area. This forms the foundation of the research presented in this thesis. For operators, the costs involved with planning and deploying additional network infrastructure to provide a dense coverage of small, high capacity cells cannot be justified. Femto-cells, however, promise to fulfil this function. These are user-deployed mini base stations (BSs), known as home evolved NodeBs (HeNBs), which are envisaged to be commonplace in homes and offices in the coming years. Since they drastically reduce communication distances to user equipments (UEs) and reuse the resources already utilised in the macro-cell, they help boost the system capacity significantly. However, there are issues to be addressed with the deployment of femto-cells, such as increased interference to the system and methods of access. These and other problems are discussed and analysed in this thesis. One of the first steps towards femtocell research has been the study of the time division duplex (TDD) underlay concept, whereby an indoor UE acts as a relay between the evolved NodeB (eNB) and other indoor UEs. In order to gain a deeper understanding of how and under what conditions such a self-organising network can be deployed, a mathematical analysis of the distribution of path losses in a network of uniformly distributed nodes has been performed. In connection with this, research has also been done in the identification of well connected nodes in such networks. Next, extensive simulations on traditional cellular networks with embedded femto-cells have been carried out in order to demonstrate the benefits of femto-cell deployment. This research has shown that femto-cells can cause severe downlink (DL) interference to badly placed macro UEs. Finally, a novel interference avoiding technique that addresses this problem is investigated.

Terrestrial free-space optical (FSO) communication uses visible or infrared wavelengths to broadcast high speed data wirelessly through the atmospheric channel. The performance of terrestrial FSO channel mainly depends on the local atmospheric conditions. Ad hoc networks offer cost-effective solutions for communications in areas where infrastructure is unavailable, e.g., intelligent transport system, disaster recovery and battlefield scenarios. Traditional ad hoc networks operate in the radio frequency (RF) spectrum, where the available bandwidth faces the challenge of rapidly increasing demands. FSO is an attractive alternative for RF in ad-hoc networks because of its high bandwidth and interference-free operation. This thesis investigates the influencing factors for routing traffic from given s-d pair while satisfying certain Quality of Services in terrestrial FSO ad hoc mesh networks under the effect of stochastic atmospheric turbulence. It starts with a comprehensive review of FSO technology, including the history, application, advantages and limitations. Subsequently the principle of operation, the building blocks and safety of FSO communication systems are discussed. The physics of atmosphere is taken into account to investigate how propagation of optical signals is affected in terrestrial FSO links. A propagation model is developed to grade the performance and reliability of the FSO ad hoc links in the network. Based on that model and the K-th shortest path algorithm, the performance of the path with highest reliability, the path with a second highest possible reliability and an independent path with no common links shared with the former two paths, were compared according to the simulation scenarios in node-dense area and node-sparse area. Matlab simulation shows that the short/long range dependent transmission delay are positively proportional to number of hops of the paths. Lower path reliability only dominate the cause of severe delay when traffic flow approaches near its upper link capacity in node-sparse area. In order to route traffic from given s-d pairs with satisfying certain Quality of Services, the path with highest reliability may not be the best choices since they may hold more hops which will degrade the QoS. Meanwhile, in case of exponential traffic congestion, it is recommended that both traffic demand and traffic flow propagating through the links should be pressed below a value close to the effective capacity, where the nonlinearity of the transmission delay curve starts to obviously aggravate.

Handheld devices are becoming increasingly common, and they have varied range of resources. Mobile Cloud Computing (MCC) allows resource constrained devices to offload computation and use storage capacities of more resourceful surrogate machines. This enables creation of new and interesting applications for all devices. We propose a scheme that constructs a high-performance de-centralized system by a group of volunteer mobile devices which come together to form a resourceful unit (cloudlet). The idea is to design a model to operate as a public-resource between mobile devices in close geographical proximity. This cloudlet can provide larger storage capability and can be used as a computational resource by other devices in the network. The system needs to watch the movement of the participating nodes and restructure the topology if some nodes that are providing support to the cloudlet fail or move out of the network. In this work, we discuss the need of the system, our goals and design issues in building a scalable and reconfigurable system. We achieve this by leveraging the concept of virtual dominating set to create an overlay in the broads of the network and distribute the responsibilities in hosting a cloudlet server. We propose an architecture for such a system and develop algorithms that are requited for its operation. We map the resources available in the network by first scoring each device individually, and then gathering these scores to determine suitable candidate cloudlet nodes. We have simulated cloudlet functionalities for several scenarios and show that our approach is viable alternative for many applications such as sharing GPS, crowd sourcing, natural language processing, etc.

Video dissemination over Vehicular Ad Hoc Networks (VANETs) is an attractive technology which supports many novel applications. Hence, the merit of this thesis has twofold. Firstly, we evaluate and compare three routing techniques and two error resilience techniques. We select a sender-based routing technique called SUV and compare it with the other two selected receiver-based routing techniques named REACT-DIS and CDS. The results, more specifically, show that the receiver-based solutions outperform the sender-based solution. In addition, only CDS method fulfils the general quality requirements as it is the best that reduces redundancy packets and covers the whole topology. The results also indicate that the video coding scheme, Interleaving, can fix the multiple consecutive packet losses and guarantee reliable video qualities over VANETs. Network Coding, however, fails to provide satisfactory video quality for urban scenarios. This study next combines the selected receiver based routing techniques and the two error resilience techniques. We find the best combination is Interleaving over CDS. Secondly, we design a quality guaranteed video dissemination protocol for urban VANETs scenarios. Based on our comparison result, our protocol selects the CDS and Interleaving as the routing and error resilient techniques. To fix the single packet loses caused by the topology’s intermittent disconnection and collisions, we propose a store-carry-broadcast scheme for the nodes to re-transmit the local buffer saved packets. The results, when compared to the selected techniques and combinations, show that our proposed protocol is the most efficient one in terms of packet delivery, delay, overhead and video quality.