A mobile social network (MSN) is defined as a mobile network that uses social relationships to allow its nodes to communicate. Many wireless networks including ad hoc networks do not reflect a real world deployment because of routing implementation difficulties. However, with the enormous use of social network sites (SNSs) including Twitter and Facebook, MSNs are expected to make the implementation of routing easier. Thus, some research activity has been devoted to routing protocols in such networks. This task is very challenging, thus only a few MSN routing protocols have been proposed in the literature. However, these protocols suffer from either a low delivery ratio or high memory requirements. This thesis presents a new routing protocol (Status) for MSNs which has excellent performance in terms of delivery ratio and memory requirements. Status takes advantage of the online status of a node to make forwarding decisions. Status has a low overhead ratio, low average delay and low computational complexity at the node level. All of these features are examined in this thesis. Simulation results are presented which show that Status outperforms other routing protocols such as Epidemic and PRoPHET with a realistic mobility model, namely, the shortest path movement based model (SPMBM). Status does not have high memory requirements since it does not store the online status of other nodes. Instead, an instance check is done when two nodes meet. Since messages are forwarded without probability calculations based on contact history, Status also has low computational complexity. / Graduate

Routing plays an important role in energy constrained Wireless Sensor Networks (WSNs). To conserve energy in WSN, energy-efficiency of the routing protocol is an important design consideration. These protocols should maximize network lifetime and minimize energy consumption. In this thesis, a novel multipath routing protocol is proposed for WSNs, which constructs multiple paths based on residual energy of the nodes. The protocol allows the source node to select a path for data transmission from the set of discovered multiple paths based on cumulative residual energy or variance. Choosing a next-hop node based on energy, and using an alternative path for routing achieves load balancing. The results show that the proposed algorithm M-VAR has lower residual energy variance (96%, 90%, 72%, 12% less) and longer network lifetime (404%, 205%, 115%, 10%) than basic Directed Diffusion, load-balanced Directed Diffusion (LBDD-ED-RD), multipath Directed Diffusion (MDD-CRE), and the proposed algorithm M-CRE, respectively.

Routing plays an important role in energy constrained Wireless Sensor Networks (WSNs). To conserve energy in WSN, energy-efficiency of the routing protocol is an important design consideration. These protocols should maximize network lifetime and minimize energy consumption. In this thesis, a novel multipath routing protocol is proposed for WSNs, which constructs multiple paths based on residual energy of the nodes. The protocol allows the source node to select a path for data transmission from the set of discovered multiple paths based on cumulative residual energy or variance. Choosing a next-hop node based on energy, and using an alternative path for routing achieves load balancing. The results show that the proposed algorithm M-VAR has lower residual energy variance (96%, 90%, 72%, 12% less) and longer network lifetime (404%, 205%, 115%, 10%) than basic Directed Diffusion, load-balanced Directed Diffusion (LBDD-ED-RD), multipath Directed Diffusion (MDD-CRE), and the proposed algorithm M-CRE, respectively.

Wireless Mesh Networks (WMNs) are bringing revolutionary change in the field of wireless networking. It is a trustworthy technology in applications like broadband home networking, network management and latest transportation systems. WMNs consist of mesh routers, mesh clients and gateways. It is a special kind of wireless Ad-hoc networks. One of the issues in WMNs is resource management which includes routing and for routing there are particular routing protocols that gives better performance when checked with certain parameters. Parameters in WMNs include delay, throughput, network load etc. There are two types of routing protocols i.e. reactive protocols and proactive protocols. Three routing protocols AODV, DSR and OLSR have been tested in WMNs under certain parameters which are delay, throughput and network load. The testing of these protocols will be performed in the Optimized Network Evaluation Tool (OPNET) Modeler 14.5. The obtained results from OPNET will be displayed in this thesis in the form of graphs. This thesis will help in validating which routing protocol will give the best performance under the assumed conditions. Moreover this thesis report will help in doing more research in future in this area and help in generating new ideas in this research area that will enhance and bring new features in WMNs. / Wireless Mesh Networks (WMNs) bringar revolutionerande förändring inom området för trådlösa nätverk. Det är en pålitlig teknik i tillämpningar såsom bredband hemma nätverk, nätverkshantering och senaste transportsystem. WMNs består av mesh routrar, kunder mesh och gateways. Det är en speciell typ av trådlöst ad-hoc-nätverk. En av frågorna i WMNs är resurshushållning som inkluderar routing och routing det finns särskilda routingprotokoll som ger bättre prestanda vid kontroll med vissa parametrar. Parametrar i WMNs omfatta dröjsmål, genomströmning, belastningen på nätet etc. Det finns två typer av routingprotokoll dvs reaktiva protokoll och proaktiva protokoll. Tre routingprotokoll AODV, DSR och OLSR har testats i WMNs under vissa parametrar som är försenade, genomströmning och belastningen på nätet. Testning av dessa protokoll kommer att utföras i den optimerade Network Evaluation Tool (OPNET) Modeler 14.5. De erhållna resultaten från OPNET kommer att visas i denna avhandling i form av grafer. Denna uppsats kommer att bidra till att godkänna vilka routingprotokoll kommer att ge bäst resultat enligt den antagna förhållanden. Dessutom kommer denna uppsats rapport kommer att bidra till att göra mer forskning i framtiden på detta område och bidra till att generera nya idéer inom detta forskningsområde som kommer att öka och att nya funktioner i WMNs. / +46762749245

Luk, Chun Pong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 122-125). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction / Motivation --- p.1 / Chapter 1.1 --- Background and Motivation --- p.1 / Chapter 1.2 --- Performance Analysis of Opportunistic Routing in Multi-hop Wireless Network --- p.3 / Chapter 1.3 --- Opportunistic Routing Protocol Design --- p.5 / Chapter 1.4 --- Chapter Summary --- p.6 / Chapter 2 --- Literature Review --- p.8 / Chapter 2.1 --- Introduction --- p.8 / Chapter 2.2 --- Opportunistic Routing Protocols --- p.9 / Chapter 2.2.1 --- Challenges of the Opportunistic Routing Protocol Design --- p.9 / Chapter 2.2.2 --- Overview of Existing Opportunistic Routing Protocols --- p.11 / Chapter 2.2.3 --- Forwarding Set Selection Algorithms --- p.12 / Chapter 2.2.4 --- Actual Forwarder Determination --- p.13 / Chapter 2.2.5 --- Duplicate Suppression Strategies --- p.14 / Chapter 2.2.6 --- Variations of Opportunistic Routing Protocols --- p.16 / Chapter 2.3 --- Performance Evaluation and Analysis of Opportunistic Routing --- p.16 / Chapter 2.4 --- Routing in Networks with Directional Antennas --- p.19 / Chapter 2.4.1 --- Performance Analysis of the use of Directional Antenna in Routing --- p.20 / Chapter 2.4.2 --- Existing Routing and MAC protocols for Networks with Directional Antennas --- p.21 / Chapter 2.5 --- Chapter Summary --- p.22 / Chapter 3 --- Performance Analysis of Opportunistic Routing in Multi-hop Wireless Network --- p.24 / Chapter 3.1 --- Introduction --- p.24 / Chapter 3.2 --- Analytical Derivation of the Expected Progress per Transmission of Opportunistic Routing --- p.25 / Chapter 3.2.1 --- Problem Formulations and Assumptions --- p.26 / Chapter 3.2.2 --- Reception Probability of a Node in a Given Region --- p.28 / Chapter 3.2.3 --- Radio Channel Models --- p.30 / Chapter 3.2.4 --- Average Progress per Transmission --- p.32 / Chapter 3.3 --- Validation and Analytical Results --- p.34 / Chapter 3.3.1 --- Results Validation --- p.34 / Chapter 3.3.2 --- Baseline Models --- p.35 / Chapter 3.3.3 --- Results and Analysis --- p.36 / Chapter 3.4 --- Further Extension of the Model --- p.40 / Chapter 3.5 --- Chapter Summary --- p.42 / Chapter 4 --- Opportunistic Routing in Multi-hop Wireless Networks with Directional Antennas --- p.44 / Chapter 4.1 --- Introduction --- p.44 / Chapter 4.2 --- Performance Analysis of Opportunistic Routing in Networks with Directional Antennas --- p.46 / Chapter 4.2.1 --- Network Model --- p.46 / Chapter 4.2.2 --- Radio Channel Models --- p.47 / Chapter 4.2.3 --- Antenna Models --- p.49 / Chapter 4.2.4 --- Expected Progress per Transmission with Directional Antenna --- p.51 / Chapter 4.2.5 --- Simulation Setup --- p.52 / Chapter 4.2.6 --- Results and Analysis --- p.54 / Chapter 4.3 --- Maximizing the Gain of Opportunistic Routing by Adjusting Antenna Beamwidth and Direction --- p.60 / Chapter 4.3.1 --- Introduction and Motivation --- p.60 / Chapter 4.3.2 --- Network Models --- p.61 / Chapter 4.3.3 --- Algorithms --- p.61 / Chapter 4.3.4 --- Results and Discussions --- p.66 / Chapter 4.3.5 --- Section Summary --- p.71 / Chapter 4.4 --- Chapter Summary --- p.72 / Chapter 5 --- Impact of Interference on Opportunistic Routing --- p.74 / Chapter 5.1 --- Introduction --- p.74 / Chapter 5.2 --- Interference Model --- p.75 / Chapter 5.3 --- MAC Protocols --- p.76 / Chapter 5.4 --- Simulation Results and Discussions --- p.78 / Chapter 5.4.1 --- Simulation Setup --- p.78 / Chapter 5.4.2 --- Baseline Models --- p.78 / Chapter 5.4.3 --- Results and Analysis --- p.79 / Chapter 5.5 --- Chapter Summary --- p.84 / Chapter 6 --- Threshold-based Opportunistic Routing Protocol --- p.86 / Chapter 6.1 --- Introduction --- p.86 / Chapter 6.2 --- Limitations of Existing Opportunistic Routing Protocols --- p.87 / Chapter 6.3 --- System Model --- p.89 / Chapter 6.4 --- Operating Principles of TORP --- p.91 / Chapter 6.5 --- Protocol Details --- p.93 / Chapter 6.5.1 --- Forwarding Set Computation --- p.93 / Chapter 6.5.2 --- Update of Forwarding Set and Remaining Transmission Counts --- p.97 / Chapter 6.5.3 --- Forwarding Threshold Computation and Details of the Packet Forwarding Process --- p.100 / Chapter 6.5.4 --- Node State --- p.101 / Chapter 6.5.5 --- Packet Format --- p.101 / Chapter 6.5.6 --- Batched Acknowledgement --- p.102 / Chapter 6.6 --- Advantages of TORP --- p.102 / Chapter 6.6.1 --- Distributed Forwarding Set Computation --- p.102 / Chapter 6.6.2 --- Threshold-based Forwarding --- p.103 / Chapter 6.6.3 --- MAC-Independence --- p.104 / Chapter 6.7 --- Protocol Extensions --- p.104 / Chapter 6.7.1 --- Implicit ACK --- p.104 / Chapter 6.7.2 --- Progress Recovery --- p.105 / Chapter 6.7.3 --- Modification of TORP for Large Networks --- p.106 / Chapter 6.8 --- Results and Discussions --- p.106 / Chapter 6.8.1 --- Simulation Setup --- p.106 / Chapter 6.8.2 --- Baseline Models --- p.107 / Chapter 6.8.3 --- Performance Evaluations and Analysis --- p.108 / Chapter 6.9 --- Chapter Summary --- p.116 / Chapter 7 --- Conclusion and Future Works --- p.118 / Chapter 7.1 --- Conclusion --- p.118 / Chapter 7.2 --- Future Work --- p.120 / Bibliography --- p.122

Devices taking part in mobile ad hoc networks (MANET) co-operate with each other to route packets by strictly adhering to the ad hoc routing protocol in use. Malicious nodes taking part in co-operative routing can launch a wide variety of attacks to reduce the utility of MANETs. The aim of secure routing protocols is to ensure that MANETs can continue to function even in the face of malicious nodes. Secure routing protocols should have measures to dissuade attackers by detecting inconsistencies, identifying the perpetrator responsible for the inconsistency, and provide means to inhibit the role of misbehaving nodes. Most existing secure routing protocols try to achieve only first step, viz., detection of inconsistencies. This dissertation research investigates and proposes efficient strategies that substantially enhance the scope of assurances provided by secure MANET routing protocols while keeping the overhead low.

Routing metrics are important mechanisms to adjust routing protocols' path selection according to the needs of a network system. However, if a routing metric design does not correctly match a particular routing protocol, the protocol may not be able to find an optimal path; routing loops can be produced as well. Thus, the compatibility between routing metrics and routing protocols is increasingly significant with the widespread deployment of wired and wireless networks. However, it is usually difficult to tell whether a routing metric can be perfectly applied to a particular routing protocol. Manually enumerating all possible test cases is very challenging and often infeasible. Therefore, it is highly desirable to have an automatic solution so that one can avoid putting an incompatible combination of routing metric and protocol into use. In this thesis, the above issue has been addressed by developing two automated checking systems for examining the compatibility between real world routing metric and protocol implementations. The automatic routing protocol checking system assumes that some properties of routing metrics are given and the system's job is to check if a new routing protocol is able to achieve optimal, consistent and loop- free routing when it is combined with metrics that hold the given metric properties. In contrast to the protocol checking system, the automatic routing metric checking system assumes that a routing protocol is given and the checking system needs to verify if a new metric implementation will be able to work with this protocol. Experiments have been conducted to verify the correctness of both protocol and metric checking systems. / Master of Science

Mobile Ad-hoc Networks (MANETs) have received considerable research interest in recent years. Because of dynamic topology and limited resources, it is challenging to design routing protocols for MANETs. In this dissertation, we focus on the scalability and efficiency problems in designing routing protocols for MANETs. We design the Way Point Routing (WPR) model for medium to large networks. WPR selects a number of nodes on a route as waypoints and divides the route into segments at the waypoints. Waypoint nodes run a high-level inter-segment routing protocol, and nodes on each segment run a low-level intra-segment routing protocol. We use DSR and AODV as the inter-segment and the intra-segment routing protocols, respectively. We term this instantiation the DSR Over AODV (DOA) routing protocol. We develop Salvaging Route Reply (SRR) to salvage undeliverable route reply (RREP) messages. We propose two SRR schemes: SRR1 and SRR2. In SRR1, a salvor actively broadcasts a one-hop salvage request to find an alternative path to the source. In SRR2, nodes passively learn an alternative path from duplicate route request (RREQ) packets. A salvor uses the alternative path to forward a RREP when the original path is broken. We propose Multiple-Target Route Discovery (MTRD) to aggregate multiple route requests into one RREQ message and to discover multiple targets simultaneously. When a source initiates a route discovery, it first tries to attach its request to existing RREQ packets that it relays. MTRD improves routing performance by reducing the number of regular route discoveries. We develop a new scheme called Bilateral Route Discovery (BRD), in which both source and destination actively participate in a route discovery process. BRD consists of two halves: a source route discovery and a destination route discovery, each searching for the other. BRD has the potential to reduce control overhead by one half. We propose an efficient and generalized approach called Accumulated Path Metric (APM) to support High-Throughput Metrics (HTMs). APM finds the shortest path without collecting topology information and without running a shortest-path algorithm. Moreover, we develop the Broadcast Ordering (BO) technique to suppress unnecessary RREQ transmissions.

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.

Today's society has developed a reliance on networking infrastructures. Health, financial, and many other institutions deploy mission critical and even life critical applications on local networks and the global Internet. The security of this infrastructure has been called into question over the last decade. In particular, the protocols directing traffic through the network have been found to be vulnerable. One such protocol is the Open Shortest Path First (OSPF) protocol. This thesis proposes a security extension to OSPF containing a decentralized certificate authentication scheme (DecentCA) that eliminates the single point of failure/attack present in current OSPF security extensions. An analysis of the security of the DecentCA is performed. Furthermore, an implementation of DecentCA in the Quagga routing software suite is accomplished.