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 ………………………………………………………………………………………………………………………………..ii
ACKNOWLEDGMENT ……………………………………………………………………………………………………………. iii
DEDICATION…………………………………………………………………………………………………………………………… iv
Table of Contents ……………………………………………………………………………………………………………………….. v
List of Figures ………………………………………………………………………………………………………………………….. viii
List of Tables …………………………………………………………………………………………………………………………….. ix
Table of Abbreviations ……………………………………………………………………………………………………………….. x
1.0 Introduction …………………………………………………………………………………………………………………………. 1
1.1 Problem Formulation ……………………………………………………………………………………………………….. 2
1.2 Research Objectives ………………………………………………………………………………………………………….. 3
1.4 Organization of Work ……………………………………………………………………………………………………….. 3
2.0 Literature Review ………………………………………………………………………………………………………………… 4
2.1 Mobile Ad hoc Network (MANET) ……………………………………………………………………………………. 4
2.2 Concepts of Opportunistic Network …………………………………………………………………………………… 4
2.2.1 Node Definition …………………………………………………………………………………………………………… 4
2.3 Difference between Mobile Ad hoc Network and Opportunistic Network ……………………………. 4
2.4 The Group Mutual Exclusion (GME) Problem ……………………………………………………………………….. 5
2.5 Evaluation of MANET GME Algorithms …………………………………………………………………………… 6
2.5.1 A Token–Based Group Mutual Exclusion Algorithm for MANETs ……………………………………. 6
2.5.2 A Group Mutual Exclusion Algorithm for Ad Hoc Mobile Networks …………………………………. 7
2.5.3 A Token based Distributed Group Mutual Exclusion Algorithm with Quorums for MANET … 8
2.5.4 Arbitration Based Distributed Group Mutual Exclusion Algorithm for Mobile Ad hoc Network ………………………………………………………………………………………………………………………………………….. 9
2.6 Summary ………………………………………………………………………………………………………………………….. 9
vi
2.6.1 Disadvantages of DAG based GME Algorithm ………………………………………………………………. 10
2.6.2 Disadvantages of Quorum based GME Algorithms …………………………………………………………. 10
3.0 Proposed Group Mutual Exclusion Algorithm for Opportunistic Network …………………………… 11
3.1 System Model …………………………………………………………………………………………………………………. 11
3.2 Working Principle of MEOP Algorithm …………………………………………………………………………… 12
3.3 The GME Problem ………………………………………………………………………………………………………….. 13
3.4 GME Algorithm for Opportunistic Network ……………………………………………………………………. 14
3.4.1 Data Structure ……………………………………………………………………………………………………………. 14
3.4.2 Messages …………………………………………………………………………………………………………………… 15
3.4.3 Initialization ……………………………………………………………………………………………………………….. 15
3.4.4 Pseodocode ……………………………………………………………………………………………………………….. 15
3.5 Explanation of the GME algorithm for OppNet ……………………………………………………………….. 19
3.5.1 Generating Request …………………………………………………………………………………………………….. 19
3.5.2 Forwarding Request ……………………………………………………………………………………………………. 19
3.5.3 Forwarding Token ………………………………………………………………………………………………………. 20
4.0 Proof of Algorithm Correctness …………………………………………………………………………………………… 22
4.1 The Mutual Exclusion Property ………………………………………………………………………………………. 22
4.1.1 Proposition ………………………………………………………………………………………………………………… 22
4.1.2 Theorem ……………………………………………………………………………………………………………………. 23
4.1.3 Proof by contradiction: ………………………………………………………………………………………………… 23
4.2 The Concurrency Property ……………………………………………………………………………………………… 23
4.2.1 Theorem ……………………………………………………………………………………………………………………. 23
4.2.2 Direct the proof: …………………………………………………………………………………………………………. 23
4.3 The Bounded Delay Property…………………………………………………………………………………………… 23
4.3.1 Theorem ……………………………………………………………………………………………………………………. 24
CHAPTER ONE
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.
Figure 1.1: Sending an email using Opportunistic Network
2
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.
Researchers have limited attention to this problem area in Opportunistic network. Tamhane in [20] proposed and simulated a novel token based Mutual Exclusion algorithm for Opportunistic network.
Over the past few decades, an interesting extension of the mutual exclusion problem known as the Group Mutual Exclusion (GME) problem, has been proposed by Joung. It is known as the Congenial Talking Philosopher [8]. Joung’s major focus is to improve upon concurrent access to a critical section by, trying to avoid delays in processes waiting to access the same resources as those processes executing the critical section. This phenomenon allows resources to be shared by processes of same group but not processes of different groups. In other words, at most one group of processes executes their critical section concurrently.
A CD jukebox is a key example of the Group Mutual Exclusion problem. Data is stored on disk,
3
and only one disk is loaded for access at a time, therefore, processes wishing to access same loaded disk can do so concurrently. To the best of our knowledge, no GME algorithm has been proposed for Opportunistic network.
1.2 Research Objectives
The main objectives of this Master’s project are to;
i. Evaluate GME algorithm for MANET and discuss their applicability to Opportunistic net-work.
ii. Propose a GME Algorithm for Opportunistic network based on some existing Algorithm.
iii. Prove the algorithm satisfies the GME Properties.
1.3 Approach Adopted
The scientific approach employed to solve the stated problem and to meet our objectives includes:
i. Evaluating the proposed GME algorithm for MANET, and based on the assumptions of each algorithm, we will determine if it is applicable to Opportunistic network.
ii. Proposing an existing Algorithm that will be modified to suit the GME problem in OPPNET.
1.4 Organization of Work
The rest of the report is organized as follows; Chapter 2 gives a survey of related work in Group Mutual Exclusion problems, and evaluation of existing Algorithms for MANET. Chapter 3 de-fines the proposed Algorithm. Proof of the Algorithm will be presented in chapter 4. Chapter 5 provides conclusion and future work.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
