EFFICIENT BEACONLESS ROUTING PROTOCOL FOR ML-MAC GRID TOPOLOGY IN WIRELESS SENSOR

(1)

PERFORMANCE EVALUATION OF ENERGY-

EFFICIENT BEACONLESS ROUTING PROTOCOL FOR ML-MAC GRID TOPOLOGY IN WIRELESS SENSOR

NETWORK

BY

MAHMUDA AKTER

A dissertation submitted in fulfillment of the requirements for the degree of Master of Science (Computer and Information

Engineering)

Kulliyah of Engineering

International Islamic University Malaysia

JULY 2018

(2)

ii

ABSTRACT

IEEE802.15.4 is a concrete challenge to provide energy-efficient communication for numerous monitoring applications in Wireless Sensor Networks (WSNs) due to the enhancements of Medium Access Control (MAC) layer specifications and topology- based routing protocols. In contention-based conventional MAC layer protocols are considered as the single-layer protocols, where the static listen or sleep scheduling technique is used. These protocols keep the channels in unwanted idle listening mode during the variation of traffics. Hence, increases the channel congestion, packets collisions and consumes more battery energy. However, to overcome these issues, some researchers propose Multi-Layer (ML-MAC) concept to control congestion and packet collisions but still consuming much unwanted energy due to routing protocols.

Conventional flooding-based routing protocols broadcast beacon frame or “hello”

message periodically to identify the optimal path to forward sensing data from source sensor to sink node resulting sensor nodes receive redundancy data from other nodes and consumes more energy in terms of both transmissions and receptions. This thesis integrates a Beaconless Routing Protocol (BLR) in ML-MAC concept for high-density grid topology which eliminates the broadcasting redundancy and conserves battery energy in sensor network. The performance evaluation of BLR-ML-MAC protocol for high-density grid topology has been carried out and benchmarked it with the conventional Ad-hoc On demand Distance Vector (AODV) ML_MAC routing protocol. The simulation results show that the energy consumption, network lifetime, jitter, end-to-end delay and throughput in the proposed scheme are significantly improved about 57.14%, 37.10%, 26.27%, 7.12% and 27.28% respectively compared to benchmark scheme.

(3)

iii

ﺚﺤﺒﻟا ﺔﺻﻼﺧ

ﻞﺜﳝ يا يا يا ٨٠٢.١.١٥.٤. ً�ﺪﲢ ﺎﻴﻌﻗاو ﲑﻓﻮﺘﻟ تﻻﺎﺼﺗا ﻢﺴﺘﺗ ةءﺎﻔﻜﻟﺑﺎ ﺔﻠﻋﺎﻔﻟا ﰲ ماﺪﺨﺘﺳا ﺔﻗﺎﻄﻟا ﲑﺜﻜﻟ ﻦﻣ تﺎﻘﻴﺒﻄﺗ ﺔﺒﻗاﺮﳌا ﰲ تﺎﻜﺒﺷ رﺎﻌﺸﺘﺳﻻا ﺔﻴﻜﻠﺳﻼﻟا (WSN) ﺐﺒﺴﺑ ﺰﻳﺰﻌﺗ تﺎﻔﺻاﻮﻣ ﺔﻘﺒﻃ ﻢﻜﺤﺘﻟا ﰲ لﻮﺻﻮﻟا ﱃإ ﻂﺋﺎﺳﻮﻟا (MAC) تﻻﻮﻛﻮﺗوﺮﺑو ﻪﻴﺟﻮﺘﻟا ﺔﻤﺋﺎﻘﻟا ﻰﻠﻋ ﺔﺳارد ﺎﻴﺟﻮﻟﻮﺑﻮﻄﻟا. ﺎﻤﻨﻴﺑ ﰲ تﻻﻮﻛﻮﺗوﺮﺑ ﺔﻘﺒﻃ MAC ﺔﻳﺪﻴﻠﻘﺘﻟا ﺔﻤﺋﺎﻘﻟا ﻰﻠﻋ ﺮﻇﺎﻨﺘﻟا ﱪﺘﻌﺗ تﻻﻮﻛﻮﺗوﺮﺑ تاذ ﺔﻴﺻﺎﺧ ﺔﻴﻘﺒﻃ ةﺪﺣاو ، ﺚﻴﺣ ﻢﺘﻳ ماﺪﺨﺘﺳا ﺔﻴﻨﻘﺗ ﺔﻟوﺪﺟ تﺎﺼﻧﻻا وأ مﻮﻨﻟا ﺔﺘﺑﺎﺜﻟا. ﻞﻤﻌﺗ ﻩﺬﻫ تﻻﻮﻛﻮﺗوﱪﻟا ﻰ ﻠﻋ ظﺎﻔﳊا ﻰﻠﻋ تاﻮﻨﻘﻟا ﰲ ﻊﺿو عﺎﻤﺘﺳﻻا ﻞﻣﺎﳋا ﲑﻏ بﻮﻏﺮﳌا ﻪﻴﻓ ءﺎﻨﺛأ فﻼﺘﺧا تﺎﻴﻠﻤﻋ ﻞﻘﻨﻟا. ﱄﺎﺘﻟﺑﺎو ، ﺐﺒﺴﺗ ﰲ ﺪﻳاﺰﺗ مﺎﺣدزا ةﺎﻨﻘﻟا تﺎﻣدﺎﺼﺗو مﺰﳊا ﻚﻠﻬﺘﺴﺗو اًﺪﻳﺰﻣ ﻦﻣ ﺔﻗﺎﻃ ﺔﻳرﺎﻄﺒﻟا. ﻊﻣو ﻚﻟذ

، ﺐﻠﻐﺘﻠﻟ ﻰﻠﻋ ﻩﺬﻫ ﻞﻛﺎﺸﳌا ، حﱰﻘﻳ ﺾﻌﺑ ﲔﺜﺣﺎﺒﻟا مﻮﻬﻔﻣ (Multi-Layer (ML-MAC) ﻢﻜﺤﺘﻠﻟ ﰲ مﺎﺣدزﻻا مﺰﺣو تﺎﻣاﺪﻄﺻﻻا ﻊﻣو اﺬﻫ ﺎ�ﺎﻓ ﻻ لاﺰﺗ ﻚﻠﻬﺘﺴﺗ ﲑﺜﻜﻟا ﻦﻣ ﺔﻗﺎﻄﻟا ﲑﻏ بﻮﻏﺮﳌا ﺎﻬﻴﻓ ﺐﺒﺴﺑ تﻻﻮﻛﻮﺗوﺮﺑ ﻪﻴﺟﻮﺘﻟا. مﻮﻘﺗ تﻻﻮﻛﻮﺗوﺮﺑ ﻪﻴﺟﻮﺘﻟا ﺔﻳﺪﻴﻠﻘﺘﻟا ﺔﻤﺋﺎﻘﻟا ﻰﻠﻋ ت�ﺎﻀﻴﻔﻟا ﺚﺒﺑ رﺎﻃإ ةرﺎﻨﻣ وأ ﺔﻟﺎﺳر " ﺎًﺒﺣﺮﻣ " ﻞﻜﺸﺑ رﺮﻜﺘﻣﻮﻳرود ﻦﻣ ﻞﺟأ ﺪﻳﺪﲢ رﺎﺴﳌا ﻞﺜﻣﻷا ةدﺎﻋ ﻹ ﻪﻴﺟﻮﺗ ت�ﺎﻴﺑ رﺎﻌﺸﺘﺳﻻا ﻦﻣ ﺮﻌﺸﺘﺴﻣ رﺪﺼﳌا ﱃإ ﺪﻘُﻋ ﻞﻴﺻﻮﺘﻟا ﺔﲡﺎﻨﻟا ﻦﻋ ﺪﻘُﻋ ﺮﻌﺸﺘﺴﳌا ﱵﻟاو ﻰﻘﻠﺘﺗ ت�ﺎﻴﺑ راﺮﻜﺘﻟا ﻦﻣ ﺪﻘﻌﻟا ىﺮﺧﻷا ، ﻚﻠﻬﺘﺴﺗو ﺪﻳﺰﳌا ﻦﻣ ﺔﻗﺎﻄﻟا ﺎﻤﻴﻓ ﻖﻠﻌﺘﻳ ﻞﻜﺑ ﻦﻣ تﺎﻴﻠﻤﻋ لﺎﺳرﻹا لﺎﺒﻘﺘﺳﻻاو .ﻩﺬﻫ ﺔﻟﺎﺳﺮﻟا ﻞﻤﻌﺗ ﻰﻠﻋ ﺞﻣﺪﻟا ﲔﺑ لﻮﻛﻮﺗوﺮﺑ ﻪﻴﺟﻮﺘﻟا ﲑﻏ يرﺎﻴﻌﳌ ا (BLR) مﻮﻬﻔﲟ ( ML-MAC ) ﺎﻴﺟﻮﻟﻮﺒﻄﻟ ﺔﻜﺒﺸﻟا تاذ ﺔﻓﺎﺜﻜﻟا ﺔﻴﻟﺎﻌﻟا ﱵﻟاو ﻲﻀﻘﺗ ﻰﻠﻋ راﺮﻜﺘﻟا ﻲﻋاذﻹا ﻆﻓﺎﲢو ﻰﻠﻋ ﺔﻗﺎﻃ ﺔﻳرﺎﻄﺒﻟا ﰲ ﺔﻜﺒﺷ رﺎﻌﺸﺘﺳﻻا.

ﰎ ﺬﻴﻔﻨﺗ ﻢﻴﻴﻘﺗ ءادأ لﻮﻛﻮﺗوﺮﺑ BLR-ML-MAC ﺔﻘﺒﻄﻟ ﺔﻜﺒﺸﻟا تاذ ﺔﻓﺎﺜﻜﻟا ﺔﻴﻟﺎﻌﻟا ﺎﻬﺳﺎﻴﻗو ماﺪﺨﺘﺳﺑﺎ لﻮﻛﻮﺗوﺮﺑ

ﻪﻴﺟﻮﺘﻟا ﱪﻋ دوﺪﳊا (AODV) ML_MAC ﺺﺼﺨﳌا ﺺﺼﺨﳌا ﺪﻨﻋ ﺐﻠﻄﻟا. ﺮﻬﻈﺗ ﺞﺋﺎﺘﻧ ةﺎﻛﺎﶈا نأ كﻼﻬﺘﺳا

ﺔﻗﺎﻄﻟا و ﺮﻤﻋ ﺔﻜﺒﺸﻟا تازاﺰﺘﻫﻻاو و ﺔﻳﺎ� ﱃإ ﺔﻳﺎ� و ﺔﻴﺟﺎﺘﻧﻹا ﰲ ﻂﻄﺨﳌا حﱰﻘﳌا ﰎ ﺎﻬﻨﻴﺴﲢ ﻞﻜﺸﺑ ظﻮﺤﻠﻣ ٪ﱄاﻮﺣ

57.14 ، 37.10٪ ، 26.27٪ ، 7.12٪ و 27.28٪ ﻰﻠﻋ ﱄاﻮﺘﻟا ﺔﻧرﺎﻘﻣ ﻊﻣ ﻂﻄﺨﳌا يرﺎﻴﻌﳌا..

(4)

iv

APPROVAL PAGE

I certify that I have supervised and read this study and that in my opinion; it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Master of Science (Computer and Information Engineering).

………

Suhaimi Abd Latif Supervisor

.…..………

Ahmad Zamani Bin Jusoh Co-Supervisor

I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Master of Science (Computer and Information Engineering).

....………

Ani Liza Bt. Asnawi Internal Examiner

...

Mashkuri Yaacob Internal Examiner

This dissertation was submitted to the Department of Electrical and Computer Engineering and is accepted as a fulfillment of the requirement for the degree of Master of Science (Computer and Information Engineering).

………

Mohamed Hadi Habaebi

Head, Department of Electrical and Computer Engineering

This dissertation was submitted to the Kulliyyah of Engineering and is accepted as fulfillment of the requirement for the degree of Master of Science (Computer and Information Engineering).

………

Erry Yulian T. Adesta

Dean, Kulliyyah of Engineering

(5)

v

DECLARATION

I hereby declare that this dissertation is the result of my own investigations, except where otherwise stated. I also declare that it has not been previously or concurrently submitted as a whole for any other degrees at IIUM or other institutions.

Mahmuda Akter

Signature:……… Date:………

(6)

vi

GE

INTERNATIONAL ISLAMIC UNIVERSITY MALAYSIA

DECLARATION OF COPYRIGHT AND AFFIRMATION OF FAIR USE OF UNPUBLISHED RESEARCH

PERFORMANCE EVALUATION OF ENERGY-EFFICIENT BEACONLESS ROUTING PROTOCOL FOR ML-MAC GRID

TOPOLOGY IN WIRELESS SENSOR NETWORK

I declare that the copyright holders of this dissertation are jointly owned by the Mahmuda Akter and IIUM.

No part of this unpublished research may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise without prior written permission of the copyright holder except as provided below

1. Any material contained in or derived from this unpublished research may be used by others in their writing with due acknowledgement.

2. IIUM or its library will have the right to make and transmit copies (print or electronic) for institutional and academic purposes.

3. The IIUM library will have the right to make, store in a retrieved system and supply copies of this unpublished research if requested by other universities and research libraries.

By signing this form, I acknowledged that I have read and understand the IIUM Intellectual Property Right and Commercialization policy.

Affirmed by Mahmuda Akter

……..……….. ………..

Signature Date

(7)

vii

“This thesis is dedicated to my dearest son (Shayaan) and family members”

(8)

viii

ACKNOWLEDGEMENTS

All glorious and pleasure is to God who created us and His final prophet and messenger, Muhammad (SAW).

All thanks go to God who makes me able to do my work with healthy and confidence and gives me all blessings upon me that I could not count.

I would like to express my thanks to A.P. Dr. suhaimi Abd Latif for being my supervisor and to Ahmad Zamani Bin Jusoh for being my co-supervisor.

My thanks also extended to those who have directly or indirectly given their support be in terms of advice, encouragement, moral or technical though minor they may seem to be.

Finally, I would like to give thanks my parents who always support me either in good moment or bad situation.

(9)

ix

LIST OF TABLES

Table 1.1 The summary of the comparison among all topologies 8 Table 2.1 The Specifications for the IEEE802.15.4 physical Layer 16

Table 2.2 The summary table of literature review 36

Table 3.1 Design parameters of the ML-MAC protocol 39

Table 3.2 Some basic simulation parameters 49

(12)

xii

LIST OF FIGURES

Figure 1.1 Bus topology 3

Figure 1.2 Tree topology 4

Figure 1.3 Star topology 4

Figure 1.4 Ring topology 5

Figure 1.5 Mesh topology 6

Figure 1.6 Circular topology 6

Figure 1.7 Grid topology 7

Figure 1.8 The flowchart of the overall research methodology 12

Figure 2.1 The communication protocol stack 17

Figure 2.2 The classification of MAC layer protocols for channel accessing 19 Figure 2.3 Basic concepts of three contention-based MAC protocols 21 Figure 2.4 The data forwarding scenario of the directed grid topology 25

Figure 2.5 A hexagonal grid topology 26

Figure 2.6 A classic grid topology 28

Figure 2.7 A weighted grid topology 29

Figure 2.8 The flowchart of the congestion control mechanism 32 Figure 3.1 The data flows of the ML-MAC and accessing policy 40 Figure 3.2 Non-overlapping layers allocation in ML-MAC protocol 40 Figure 3.3 Forwarding area and potential forwarders A and B towards sink D 46

Figure 4.1 Comparison of network lifetime analysis 53

Figure 4.2 Comparison of consumed battery capacity analysis 54

Figure 4.3 Comparison of jitter analysis 55

(13)

xiii

Figure 4.4 Comparison of end-to-end delay analysis 56

Figure 4.5 Comparison of throughput analysis 57

(14)

xiv

LIST OF ABBREVIATIONS

ACK Acknowledgement

ADC Analog to Digital Converter

AODV Ad-hoc On demand Distance Vector

BLR Beaconless Routing

CAP Contention Access Period

CDMA Code Division Multiplexing Access

CPU Central Processing Unit

CSMA Carrier Sense Multiple Access

CSMA/CA Carrier Sense Multiple Access with Collision Avoidance

DFD Dynamic Forwarding Delay

DSSS Direct Sequence Spread Spectrum FDMA Frequency Division Multiplexing Access

FFD Full Function Device

GAF Geographic Adaptive Fidelity

GBCR Grid-Based Coordinated Routing GBGR Grid-Based Geographical Routing

GMCAR Grid-based Multi-path Collision Avoidance Routing

GPS Global Positioning System

IEEE Institute of Electrical and Electronics engineers ISM Industrial, Scientific and Medical

IVC Inter-Vehicle Communication

LLC Logical Link Control

(15)

xv

LPL Low Power Listening

LQI Link Quality Identification

MAC Medium Access Control

MANET Mobile Ad-hoc Network

ML-MAC Multilayer-MAC

OSI Open System Interconnection

PAN Personal Area Network

QoS Quality of Service

RFD Reduce Function Device

S-MAC Sensor-MAC

TDMA Time Division Multiplexing Access

VANET Vehicle Ad-hoc Network

WPAN Wireless Personal Area Network

WSN Wireless Sensor Network

Z-MAC Zebra-MAC

(16)

xvi

LIST OF SYMBOLS

(i,j) Bi-dimensional coordinates Add-delay Dynamic forwarding delay

B Adjacent cell

Cav Data transmission cost

D Sink sensor node

d Distance

EnergyFullbattery Full battery energy EnergyResidual Residual battery energy

i Horizontal index

j Vertical index

M Horizontal hop

Max-delay System parameter

N Vertical hop

O Sensor cell

P Node progress towards

Pktcurrent Current received packet

Pktintermediate Intermediate received packet

Pktreceived Ending of packet received time

Pktreceived Total receiving packets in server

Pktsending Starting time of sending packet

Pktsending Total sending packets from the stations

Pktsuccess Total successful delivery packets

(17)

xvii

PRX Receiving power

PTX Transmission power

r Radius/distance

X Width

Y Height

λ Transmission cost

(18)

1

CHAPTER 1 INTRODUCTION

1.1 BACKGROUND

A group of specialized transducers have communication infrastructure and intend to monitor and record conditions at diverse locations is called Wireless Sensor Network (WSN) (Bhattacharyya, Kim, & Pal, 2010). In other words, it is a deployment of sensor devices equipped to perform a collaborative measurement process. A WSN is formed with a large number of sensor nodes that are low-power multi-functional and operated within an unattended environment. These sensor nodes have the capabilities of sense, computation and communication. A sensor unit, a Central processing unit (CPU), an Analog to Digital converter (ADC), a communication unit as well as a power unit are the basic components of a sensor node (Prashant, Varun, Raj & Devendra, 2015). In a WSN, sensor nodes do not need any pre-existing communication infrastructure since they communicate wirelessly among them (Sazak, & Abdullah, 2009). That is why, it is suitable for non-reachable places like mountains, deep forests, over the sea or rural areas. In Addition, implementation costs are also relatively cheap. However, there are some constraints sensor nodes in WSN (Prashant et al., 2015) such as low power processor, limited storage, low data rate, limited transmission range and limited power which often not possible to replace or recharge. Routing and flooding are the two data propagation mechanism that improve the efficiency of the network topologies. In WSN, usually three different network architecture have been used that are distributed network which spatially distribute autonomous sensor nodes to monitor various remote monitoring application and to send the extracted data through the network towards

CHAPTER ONE

(19)

2

destination. In addition, hierarchical network, sensor nodes are partitioned into different clusters and one of the sensor node select as the cluster head of a cluster. Each sensor node send data to the respective cluster head and it send data to the destination. Another is cluster based architecture which as like hierarchical architecture where, each cluster can communicate with other clusters and finally send data towards the destination.

(Akyildiz, Su, Sankarasubramaniam, & Cayirci, 2002). Researchers have been developed these architectures to monitor different types of monitoring applications such as weather monitoring, landslide monitoring, battle field monitoring, industrial monitoring, patient monitoring, environmental observation and forecasting, agriculture monitoring, real time traffic monitoring, intrusion detection, inventory control, fire detection in the forest, flood detection, water quality monitoring and so on (Akyildiz et al., 2002; Dargie, & Zimmerling, 2007; Zennaro, Pehrson, & Bagula, 2008). In order to monitor these applications, the WSNs have different patterns of connectivity of sensor nodes. Active sensor nodes and wireless connection among them can be defined as the form of network topology. There are three types of topologies exist in WSN for example, (i) bus, (ii) tree, (iv) star, (v) ring, (vi) mesh, (vii) circular and (viii) grid (Sharma, Verma, & Sharma, 2013). The structures of these topologies, its merits, demerits are discussed in the following sub-sections.

1.1.1 Bus Topology

Figure 1.1 presents the connectivity of bus topology. In bus topology (Wu, Chu, Pan, &

Yang, 2006), if one node wants to send a message first it broadcast that message to another node of the network. All nodes of the network can see the message but only the intended recipient receives and processes the message. Other nodes discard the

(20)

3

message. This topology is simple to install and best for limited number of nodes.

However, it has a congestion-controlling problem due to single communication path.

Sensor Node

Figure 1.1: Bus topology

1.1.2 Tree Topology

Tree topology (Wu, Fahmy, & Shroff, 2008) uses a root node that is the main communication router is called central hub. Parent nodes are ascendants that maintain the children nodes (descendants). Children nodes sense the data and send it to parent node. Afterwards, parent nodes forward the data to upper level or sink node. The communication path of this topology can be single hop or multi hop. This topology is easy to maintain and node expansion is easy and possible as well. However, installation cost is higher and this topology becomes difficult to maintain for huge nodes. Figure 1.2 shows the structure of the tree topology.

(21)

4

Sensor Nodes Root

Center Hub

Figure 1.2: Tree topology

1.1.3 Star Topology

In star topology (Yang, He, & Shao, 2010), nodes cannot communicate directly with each other rather than via a centralized communication hub. This centralized hub acts as a router for whole communication system. Setup, modification, troubleshooting, hub up-gradation is easy though its’ installation cost is high and it is expensive to use. In this topology, failure of one node cannot affect the network but if hub is affected then the entire network stops working. Figure 1.3 represents the architecture of star topology.

Sensor Nodes

Sink

Figure 1.3: Star topology

(22)

5 1.1.4 Ring Topology

In a ring topology (Ren, Chen, Yao, & Li, 2012), each node has exactly two neighbor nodes to communicate and this communication occurs through the same direction, either “clockwise” or “counterclockwise”. Therefore, failure of one node breaks the loop and entire network goes down. This network is cheap to setup but difficult in troubleshooting. Figure 1.4 displays the configuration of ring topology.

Sensor Nodes

Figure 1.4: Ring topology

1.1.5 Mesh Topology

In the mesh topology (Vinh, Quynh, & Quynh, 2012), several paths have been used to send messages from source to destination. If each node is connected directly to every other node of the network then called full mesh. Otherwise, that is partial mesh where connectivity exists between all the nodes but some of them is indirectly connected to others. If any node is failed then another path exists because the network automatically reconfigured itself. This network is difficult to install and more costly. Figure 1.5 presents the setup of the mesh topology.

(23)

6

Sensor Nodes

Sink

Figure 1.5: Mesh topology

1.1.6 Circular Topology

In circular network (Sharma et al., 2013), a circular sensing area is surrounded a sink, that is the center of this network. Sensor nodes sense the information and transmit them to the center or sink. This network is easy to install and maintain and more energy efficient. Figure 1.6 shows the structure of the circular topology.

Sensor Nodes Sink

Random Nodes Sensor Nodes on

the Diagonal

Network’s Circles

Figure 1.6: Circular topology

(24)

7 1.1.7 Grid Topology

In grid topology (Liu, Wang, Zhang, & Wang, 2010), sensor networking area is divided into non-overlapping same sized square grids. Each grid should have minimum one node and not more than that in working state at any time. One node is selected from each grid as a grid head that is responsible for forwarding information and transferring data packets. Figure 1.7 highlights the configuration of grid topology.

Sensor Nodes Master Nodes

Sink Node

Figure 1.7: Grid topology

Table 1.1 presents the summary of the comparison among all topologies of wireless Sensor Network.

EFFICIENT BEACONLESS ROUTING PROTOCOL FOR ML-MAC GRID TOPOLOGY IN WIRELESS SENSOR

PERFORMANCE EVALUATION OF ENERGY-