ABSTRACT
The Opportunistic network is an interesting development in the Mobile Ad hoc Network (MANET) environment. It has no end-to-end connectivity among nodes.
Unlike MANETs, the nodes in Opportunistic network are independent on network topology. Resources are constrained, and nodes share resources in this type of network. Hence, to ensure the integrity of nodes wishing to access a shared resource, mutual exclusion is required to allow nodes to access shared resources exclusively.
In this thesis, we review an extension of the mutual exclusion problem known as, the Group Mutual Exclusion (GME) for MANETs, and evaluate their applicability to Opportunistic network. We further propose a token based Group Mutual Exclusion Algorithm for Opportunistic network. The MEOP algorithm in [20] is adapted for the proposed algorithm and to ensure concurrent execution of critical section, a similar approach is adopted from [21], [9]]. The algorithm ensures mutual exclusion, bounded delay and concurrent entering properties.
TABLE OF CONTENTS
ABSTRACT
Table of Contents
List of Figures
List of Tables
Table of Abbreviations
CHAPTER ONE
1.0 Introduction
1.1 Problem Formulation
1.2 Research Objectives
1.4 Organization of Work
CHAPTER TWO
2.0 Literature Review
2.1 Mobile Ad hoc Network (MANET)
2.2 Concepts of Opportunistic Network
2.2.1 Node Definition
2.3 Difference between Mobile Ad hoc Network and Opportunistic Network
2.4 The Group Mutual Exclusion (GME) Problem
2.5 Evaluation of MANET GME Algorithms
2.5.1 A Token–Based Group Mutual Exclusion Algorithm for MANETs
2.5.2 A Group Mutual Exclusion Algorithm for Ad Hoc Mobile Networks
2.5.3 A Token based Distributed Group Mutual Exclusion Algorithm with Quorums for MANET
2.5.4 Arbitration Based Distributed Group Mutual Exclusion Algorithm for Mobile Ad hoc Network
2.6 Summary
2.6.1 Disadvantages of DAG based GME Algorithm
2.6.2 Disadvantages of Quorum based GME Algorithms
3.0 Proposed Group Mutual Exclusion Algorithm for Opportunistic Network
CHAPTER THREE
3.1 System Model
3.2 Working Principle of MEOP Algorithm
3.3 The GME Problem
3.4 GME Algorithm for Opportunistic Network
3.4.1 Data Structure
3.4.2 Messages
3.4.3 Initialization
3.4.4 Pseodocode
3.5 Explanation of the GME algorithm for OppNet
3.5.1 Generating Request
3.5.2 Forwarding Request
3.5.3 Forwarding Token
CHAPTER FOUR
4.0 Proof of Algorithm Correctness
4.1 The Mutual Exclusion Property
4.1.1 Proposition
4.1.2 Theorem
4.1.3 Proof by contradiction:
4.2 The Concurrency Property
4.2.1 Theorem
4.2.2 Direct the proof:
4.3 The Bounded Delay Property
4.3.1 Theorem
4.3.2 Proof:
CHAPTER FIVE
5.0 Conclusion and Future Work
5.1 Conclusion
5.2 Future Work
Bibliography
CHAPTER 1
1.0 Introduction
Opportunistic Network is an interesting development in Mobile ad hoc Network (MANET) environment and a promising technology in achieving the vision of pervasive computing. The Opportunistic network [16] is designed from mobile wireless network devices that have good sensing capabilities, good memory, and short radio transmission functionality. These devices are usually carried by human, animal, vehicles, among many others.
The exceptions in Opportunistic Network such as network failure, node failure and infrequent node contact mostly result from battery failure and power management of these devices. Regardless, the mobility of these devices is used as an advantage to create an Opportunistic net-work. The mobility nature of these wireless devices is utilized to create communication between nodes when route connecting them never exited or there is no direct contact with the internet.
The network is usually partitioned into regions; nodes are interconnected by operating in a store-carry forward manner. A node can store carry and forward messages within the same region or different regions acting as a router or a gateway respectively, node can also be a host where data is finally stored [6].
The nodes in Opportunistic Network are independent of the network topology but not the case in MANET. Routes in Opportunistic Network are not predetermined. While a message is in route from source to destination, all nodes have the opportunity to serve as the next hop provided it is closer to the destination.
Illustrated in Figure 1.1 [15], is an example that describes how opportunistic network operates in real life. A lady with a laptop at the bottom end in Figure 1.1 is trying to send a mail to a friend. The following steps ensure delivery of the message;
· The lady transfers the mail via Wi-Fi link to the bus passing within the area hoping the bus will transfer the message closer to her friend.
· A device somewhere in the bus then transfers the message to the lady with a phone along the way, also hoping it is closer to the intended destination.
· The lady’s phone identifies a wireless network device carried by a pet and transfers the message to it.
· The man not far from the destination finally transfers the email to her friend via Wi-Fi link
The mobility nature of the network has drawn the attention of researchers to focus more on routing and data forwarding. The routing protocol in Opportunistic Network is classified into three categories: Mobility class, context–oblivious and social context–aware routing [5]. In [10] Lilien discussed the challenges in security and privacy in Opportunistic network.
1.1 Problem Formulation
An Opportunistic network is a typified distributed system and resources are constrained in distributed systems, thus processes or nodes share resources. To ensure the integrity of nodes wishing to access a shared resource, mutual exclusion is required. This allows nodes to exclusively access a shared resources, in other words to execute critical section. Mutual exclusion ensures that, at most one node executes the critical section at a time. Mutual exclusion algorithms are evaluated by the number of messages generated per critical section entry, synchronization delay, concurrency and size of information control.....
================================================================
Item Type: Project Material | Size: 36 pages | Chapters: 1-5
Format: MS Word | Delivery: Within 30Mins.
================================================================
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.