Energy Efficient And Time Saving Mechanism For Manets Computer Science

Essay add: 20-10-2016, 17:37   /   Views: 8

This paper propose an efficient way for saving energy and total network time as well as increasing the network life time. The entire network is divided into clusters using cone based topology control algorithm. It is assumed that each node know their position and angle to its neighbours. We describe four algorithms to achieve multi level objectives. The total topology is considered as two level graphs, one is formed by nodes in the cluster and another formed by cluster heads. The approach described here is a synchronous method by which optimal path algorithm run simultaneously in clusters to reduce the total network delay and achieve high speed in transmission.

Energy efficiency is the major issue in all kind of wireless networks. Although semiconductor technology advances very rapidly, the development in battery efficiency is very slow compared to that. So an energy efficient model is necessary to resolve this issue. Energy efficiency can be achieved any layer of the protocol stack however most of the work belongs to data link layer and network layer. Different techniques have been suggested by researchers, topology control based approach is one among them. Topology control can be defined as technique to generate a network with desired properties (like connectivity, biconnectivity...etc) and it increase the network capacity while reducing the energy consumption.

Power consumption of each node belongs to three categories according to functionality they are 1) power utilised during transmission of packet 2) power utilised during reception of packet 3) power utilised while system is idle. Power consumption during idle time is almost equal to power consumption in sleep mode and hence it can be negligible, but power consumption during communication is to be taken into account because of its high level power consumption. Using power efficient path repeatedly may not be a good solution because it causes to reduce the total network life time. It is due to the fact that some nodes in the critical path are depleted along the time.

In this paper we propose 4 algorithms for energy efficient routing with increased life time. Our inter cluster approach reduce the total network time by selective participation of clusters. Main idea behind this is not to disturb those clusters which are not part of the global path. We put some initiator node randomly by considering proximity of nodes and centrality of the network. Initiator initiates the topology creation by creating two level of graph. It uses cone based topology control algorithm to find the nearest neighbours. With CBTC algorithm initiators keeps increasing its power until it has at least one neighbouring node in every α cone or it reaches maximum power limit. In the first power level it select one node as cluster head from a set of nodes in that cone .we simply consider it as child cluster head since it is near to the initiator. It is assumed that communication range increases monotonically with transmission power.α<=2π/3 is the necessary condition to ensure that network is connected in CBTC algorithm. Initiator find a set of nodes with maximum power level and it select a node as parent cluster head with some selection criteria. Criteria may be high level of energy, more proximity with neighbours or the less distance with outer nodes...etc.

related work

Our algorithm is based on the clustering concept and cone based toppogy control algorithm

The CBTC (cone based topology control) protocol [4] is a direction based distributed topology control algorithm in which each node know the angle to its neighbours .the idea behind CBTC is similar to that used in yao graph, both divide the plane in to cones. In this paper we used the CBTC algorithm to divide cluster into 4 quarters and to find the cluster head within the sub clusters at each cone.XTC protocol[5]is neighbour based distributed topology control algorithm works without location or directional information and it preserves worst-case connectivity. This algorithm consists of three main steps: neighbour ordering, neighbour order exchange and edge selection. In the first step each node broadcasts once at maximum power and then rank all its neighbours according to its link quality such as Euclidian distance, signal attenuation or packet arrival rate, to the second step the neighbour order information is exchanged among all neighbours. Typically a node u broadcasts its own neighbour order while receiving the orders established by all of its neighbours.During the third step,each node locally selects all of its neighbours in the order of its ranking and decides which one need to be linked directly.



In this architecture nodes are deployed randomly and are grouped into clusters with central initiator node. Clusters formed by the initiator should not overlap each other. We assume the nodes are homogeneous and use Omni directional antenna for transmission. Clusters can be formed based on some criteria such as communication range proximity and geographical location. In this paper we assume that nodes and initiators are stationary for a particular time period and all the nodes in the clusters are covered by initiator. Initiator use a cone based topology control and divide the cluster into 4 quarter; quarter1 to quarter4.Each quarter has at least 2 header nodes. The node which is very near to initiator in cone α is called child cluster head and the node which requires maximum power to reach, in the same cone/quarter is called parent cluster head selection of cluster head depends on several criteria like maximum battery power, more proximity to neighbouring nodes...etc. In later section we mentioned cluster which is original sub cluster in this scenario.


Four algorithms are proposed to achieve multiple objectives. These objectives are to find path between source to destination by considering different aspects such as reduce the end to end delay between source and destination, bypass the route by excluding those node which has battery level less than threshold level, find global path for efficient selection of clusters in participation of data transmission and provide synchronisation among these clusters to achieve reduced network time.

Inter cluster algorithm to find global path

Set of cluster heads and initiator nodes form a graph Gglobal.

Let Shead be the source cluster head(parent/child cluster head of the cluster in which original source node can be found)

Dhead be the destination cluster head.

Global path is a path formed by set of cluster heads and is retuned by the optimal path algorithm

Globalpath= getpathfrom(optimalpath(Shead,Dhead,"global")

Send TREQcluster packet along the global path to inform those clusters which are needed to be participated in the Data transmission and let them to find the local path simultaneously to achieve speed objective (time saving).

We introduce a new graph comprised with cluster heads and initiators. There are two cluster heads in each cluster; child cluster head and parent cluster head. By this algorithm we find out a global and efficient path between the cluster heads in terms of energy efficiency and distance. This path is termed as "Global path". The source cluster head and destination cluster head connect the global path .One of the cluster head of cluster which contain source is taken as source cluster head and one of the cluster head of cluster which contain destination is taken as destination cluster head There may be a cluster which contain source as well as destination. In that case global path connect 2 cluster heads and have least length but it does not result in long optimal path since the optimal final path is the merging of global and local paths, within the cluster it takes the local path obtained by intra cluster.

Global path is obtained by a global algorithm called optimal path algorithm. We mention it as global algorithm in the sense that it is used by both intra cluster and inter cluster algorithms. The path is extracted from the algorithm using a function getpathfrom .The optimal path obtained can be run only for time't' ,since after 't' optimal path become less optimal than near optimal. After finding global path it send Transmission Request packet TREQcluster along the global path to inform those clusters which are to be participated in the data transmission. After getting this packet intercluster algorithm run on those participating clusters simultaneously to find local path within the cluster .This is the way how our algorithm reduce the total network delay.


Global path


Fig1: finding global path among the cluster heads and initiators.

Intra cluster algorithm to find local path

set of nodes within the cluster form a graph called Glocal

2.Let S be the source and D be the destination

If the cluster contain original source set S=original source

Else S=cluster head*1

If the cluster contain original destination

then set d= original destination

Else D=cluster head*2

Local path =getpathfrom(optimal path(S,D,"local")

Intra cluster algorithm find local path within the cluster a- fter getting TREQcluster packet from the global path. Nodes within the cluster together form a graph called Glocal .The local path connect the source and destination together within the cluster .If the cluster contain original source then the source become the original source else it takes one of the cluster head as source .The selection of cluster head as source depends on the 1st occurrence of the cluster head within the global path towards the direction of original destination or the proximity with original source. If the cluster contains original destination then the destination become original destination otherwise it would take one of the cluster head depends on the 2nd occurrence towards the original destination or the proximity with original destination. Like inter cluster algorithm intra cluster algorithm find out the local path within the cluster using same optimal path algorithm with parameters different.

Fig a. With no original source or destination

Fig b .Cluster with original source.

Fig c.Cluster with original destination

Fig d Cluster with original source and destination



Local path



Algorithm optimal path(s,d,label)

Find the set of optimal path in terms of power efficiency if the label is local take power consumption as metric otherwise distance

Let Zlabel be the optimal path set

Find the set of optimal path in terms of network life time Wlabel

Find the set of path such that Xlabel =Zlabel ∩ Wlabel

Sort Xlabel in the order of its power efficiency


Optpath =first path in Xlabelfor time 't'

Near optpath=next path in Xlabel

During time t

If any node exhaust(Batt current power


After time t

Optpath= Near optpath

Near optpath=next path from Xlabel

Until no path exists in Xlabel

Optimal path algorithm find the set of path with less power consumption and increased network life time.The parameter label is used to describe whether it is called by inter cluster or intra cluster algorithm .If the label is "global"it find global path otherwise it find the local path within the cluster. It first find a set of paths with less power consumption using dijkstra's algorithm .then it find set of paths with high network life time and finally the intersection of these two sets form a set of optimal paths. This set is sorted in term of energy efficiency to get the most optimal path second in the set would be the near optimal path .optimal path either local or global is used only for a period of time 't', because after this time period the optimal path become less optimal than the near optimal path. The value of 't' can be defined as how many times optimal path is optimal compared to near optimal .During this time 't' some nodes may get depleted ,if happened so algorithm call a bypass algorithm to exclude that node and again run inter cluster or intra cluster depending upon the label.after period 't' near optmal path become optimal path and optimal path is added to the path inthe sorted set X become near optimal path . This paths are valuable for time period 't' n the process repeats until no path exists in the set X.

Algorithm Bypass(nodei,label) todiscard

If the label is" global "

It sends a resign packet to the initiator to select one head to play its role

Initiator send an agree packet to nodei

After getting agree packet it goes to sleep mode

Else //label is "local"

It sends resign packets to the neighbouring nodes and after getting acknowledgement it goes to sleep mode.

Until it gets fully recharged and send a join packet

Bypass algorithm is used to exclude some nodes which do not have enough battery power, from participating data transmission. For cluster head it sends a resign packet to the initiator node so that it can select another cluster head to play its role. After selecting cluster head it send an agree packet to the cluster head. Cluster head goes to sleep state and keeps that state until it get fully recharged. On getting full charge It sends a join packet to initiator to inform that it is ready to participate in data transmission only when current cluster head of same type send aresign packet to the initiator.For the label "local" the node send a resign packet to the neighbours. It goes to sleep state (after getting acknowledgement from its neighbours) until it get fully recharged. On getting full charge It send a join packet to the neighbours to inform that it is ready for participation.

Purpose of child cluster head :

Parent cluster head cannot communicate with initiator (for eg to send resign packet)with less power so it communicate via child cluster head .parent cluster head and child cluster head are connected through a local path obtained with optimal path algorithm.

Participation in finding the optimal global path

Purpose of parent cluster head :

Initiator and child nodes cannot communicate with other nodes and initiator which are far away from parent nodes are used to reduce the gap between other initiators and parent nodes.

Participation in finding optimal global path.

Final path:

The final optimal path can be obtained by merging the global path and local path .

Fig local path and globalpath

The path with thick line shows the global path and thin line show s the local path.

Fig:final optimal path merge of global and local path

The local path shows the optimal path from sourcecluster head to destination cluster head


In this work, we presented a topology control technique using four algorithms for achieving three objectives energy efficiency, maximum life time of network and maximum network speed.

Future research direction could be based on routing and initial throughput consideration in networks and also an optimal way to power control within sub clusters


The heading of the Acknowledgment section and the References section must not be numbered.

Causal Productions wishes to acknowledge Michael Shell and other contributors for developing and maintaining the IEEE LaTeX style files which have been used in the preparation of this template. To see the list of contributors, please refer to the top of file IEEETran.cls in the IEEE LaTeX distribution.

Article name: Energy Efficient And Time Saving Mechanism For Manets Computer Science essay, research paper, dissertation