Scheduling the Packets by Using Chromatic Graph Colouring in Mesh Network Through NS2

Scheduling the Packets by Using Chromatic Graph Colouring in Mesh Network Through NS2

R. L. Divakar, P. Madhuri U. BhanuMurthy

Assistant Professor, B.Tech student, B.tech student,

Dept. of CSE,LIET, Dept. of CSE,LIET, Dept. of CSE,LIET,

Vizianagaram,AP. Vizianagaram,AP. Vizianagaram,AP.

T. Geetha Sravya

B-Tech student, Dept.of CSE LIET,Vizianagaram,AP

Abstract

We consider a wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of heavy traffic pattern. We use DSDV, a table driven routing protocol scheme for adhoc mobile networks based on the BELLMAN FORD algorithm. The main contribution of the algorithm is to solve the routing loop problem and seek to schedule the routes links to maximize the number of packets that get delivered to the destination by using sequence number. Our approach is to construct an undirected graph G and to heuristically obtain a chromatic graph coloring for G that can turned into efficient link scheduling. Here, we will color the graph by using chromatic graph coloring method. The main advantage of this approach is by using DSDV routing algorithm is its performance is significantly superior to the others. For security purpose we are consider SDSDV routing algorithm. If any link failure occurs by using the DSDV then we will use chromatic graph coloring by this we will

Decrease the usage of colors and we can send the packets frequently

.Keywords: Node, DSDV, Mesh network, Chromatic graph colouring.

Introduction

In this proposed system we are using Nodes, Mesh network, chromatic graph colouring, DSDV protocol.

Node means: In communication networks a node (Latin nodus, knot) is a connection point, a redistribution point or a communication endpoint

(some terminal equipment). The definition of a node depends on the network and protocol layer referred to. A physical network node is an active electronic device that is attached to a network, and is capable of sending, receiving, or forwarding information over a communications channel.[1] A passive distribution point such as a distribution frame or patch panel is consequently not a node.

Mesh network means: A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways. The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic to and from the gateways which may, but need not, connect to the Internet. The coverage area of the radio nodes working as a single network is sometimes called a mesh cloud. Access to this mesh cloud is dependent on the radio nodes working in harmony with each other to create a radio network. A mesh network is reliable and offers redundancy. When one node can no longer operate, the rest of the nodes can still communicate with each other, directly or through one or more intermediate nodes. The animation below illustrates how wireless mesh networks can self form and self heal. Wireless mesh networks can be implemented with various wireless technologies.

DSDV means: Destination-Sequenced Distance- Vector Routing (DSDV) is a table-driven routing scheme for adhoc networks based on the Bellman-

Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the rooting loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.

For example the routing table of Node A in this network is

Naturally the table contains description of all possible paths reachable by node A, along with the next hop, number of hops and sequence numbers.802.11, 802.15, 802.16 cellular technologies or combinations of more than one type.

Mesh network means: .The chromatic number of a graph G the minimum number of colours required to colour the vertices of graph G.It will cover up to mesh network range.

TDMA means: Time division multiple access (TDMA) is a channel access method for shared medium networks. It allows several users to share the same frequency channel by dividing the signal into different time slots. The users transmit in rapid succession, one after the other, each using

its own time slot. This allows multiple stations to share the same transmission medium (e.g. radio frequency channel) while using only a part of its channel capacity.

Description of proposed system

In the existed proposal they consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. They assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes links to maximize the number of packets that get delivered to their destinations per time slot. Their approach is to construct an undirected graph G and to heuristically obtain node multi colourings for G that can be turned into efficient link schedules. In G each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. They present two multi colouring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multi colouring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. They have found that, as a consequence, its performance is significantly superior to the others. Owing to their numerous advantages, wireless mesh networks constitute a promising solution for community networks and for providing last-mile connections to internet users. However, like all wireless networks WMNs suffer from the problem of decreased as they become denser. In this case attempting simultaneous transmission causes interference to increase significantly. They take one common solution to reduce interference is adopt some contention free TDMA protocol and schedule simultaneous transmissions for activation only if they do not interfere with one another. In this proposal there is one drawback that is if we use a TDMA protocol then in a particular time interval the message must be transferred to the destination if not the message must be loss. In this existed proposal they schedule the packets by using the method called Multi colouring of a graph. An ad hoc network is a collecion of mobile nodes forming an instant network without fixed topology. In such a network, each node acts as both router and host simultaneously, and can move out or join in the network freely. The instantly created network

does not have any base infrastructures as used in the conventional networks, but it is compatible with the conventional networks. DSDV is a modification of the conventional Bellman-Ford routing algorithm. It addresses the drawbacks related to the poor looping properties of RIP in the face of broken links. The modification adapted in DSDV makes it a more suitable routing protocol for ad hoc networks. This paper reviews the DSDV protocol, and analyzes the properties of DSDV when it is used for ad hoc networks routing. Ad hoc networks differ significantly from conventional networks in the dynamic topology of interconnections and automatic administration for setting up the network. From a graph theory point of view, an ad hoc network is a graph G(N, E(t)), which composes of a set of nodes N, and a set of edges E(t). Each mobile host can be a node of the graph. Each edge of the set E(t) is formed by two nodes within the service range, it can be unidirectional or bi- directional. E(t) changes with time as the mobile nodes in the ad hoc network freely move around. The topology of the ad hoc can be arbitrary at any time. With the change of the topology of an ad hoc network, the nodes in the network have to update their routing information automatically and instantly. Routing protocols in packet-switched networks traditionally use either distance-vector or link-state routing algorithm. Both of them allow a host to find the next hop to reach the destination via the shortest path. The metric of the shortest path might be number of hops, time delay in milliseconds, total number of packets queued along the path, or something similar. Such shortest path protocols have been successfully used in many dynamic packet switched networks. In principle, any such protocol can also be used in ad hoc networks. The main drawbacks of both link-state and distance-vector protocol are that they take too long to converge and have a high message complexity. Link failure is the main drawback of this algorithm so here we are using chromatic graph

BLOCK DIAGRAM:

In a mesh topology each of the network node, computer and other devices are interconnected with one another. Every node not only sends its own signals but also relays data from other nodes. The chromatic number of a graph G the minimum number of colors

required to color the vertices of graph G.It will cover up to mesh network range.

1. Problems in TDMA protocol:

   1. In the certain time limit if the packet cannot reach the node it causes the packet loss.

   2. There is a chance of interference due to multi path distortion.

   3. Due to increasing the packet loss it leads to decrease the performance.

2. Advantages of DSDV Protocol:

   • Destination sequenced distance vector routing (DSDV) is adapted from the convention routing Information Protocol (RIP) to ad hoc networks routing.

   • It adds a new attribute, sequence number, to each route table entry of the conventional RIP. Using the newly added sequence number, the mobile nodes can distinguish stale route information from the new and thus prevent the formation of routing loops.

   1. There is no time limit to transmit the packets from node to node and it maintains all the information regards to each node.

   2. There is no question of interference and it maintains sequence numbers to each node.

   3. Packet loss will be decrease it leads to increase the performance of the system.

1. Packet Routing and Routing Table Management in DSDV:

   • Each mobile node of an ad hoc network maintains a routing table, which lists all available destinations, the metric and next hop to each destination and a sequence number generated by the destination node.

   • Using such routing table stored in each mobile node, the packets are transmitted between the nodes of an ad hoc network.

   • Each node of the ad hoc network updates the routing table with advertisement periodically or when significant new information is available to maintain the consistency of the routing table with the dynamically changing topology of the ad hoc network.

   • Immediately when network topology changes are detected, each mobile node advertises routing information using broadcasting or multicasting a routing table update packet.

   • The update packet starts out with a metric of one to direct connected nodes. This indicates that each receiving neighbour is one metric (hop) away from the node. It is different from that of the conventional routing algorithms.

   • After receiving the update packet, the neighbours update their routing table with incrementing the metric by one and retransmit the update packet to the corresponding neighbours of each of them.

   • The process will be repeated until all the nodes in the ad hoc network have received a copy of the update packet with a corresponding metric.

   • The update data is also kept for a while to wait for the arrival of the best route for each particular destination node in each node before updating its routing table

   • If any link failure occurs in DSDV then we will go for alternative techniques but it cannot find effective link updating so we are considering chromatic graph colouring to detect and correct link failures effectively.

2. Algorithm1:

   Step1: form a network with a limited set of nodes

   Step2: draw a table which contains all information about the node those are destination, next hop, metric, sequence number

   .

   Step3: update the table for every 30 seconds.

   Step4: if any link or node fail occurs the corresponding metric will be change.

1. Before adding chromatic graph colouring

2. After adding chromatic graph colouring:

Chromatic graph

In a mesh topology each of the network node, computer and other devices are interconnected with one another. Every node not only sends its own signals but also relays data from other nodes. The chromatic number of a graph G the minimum number of colours required to colour the vertices of graph G .It will cover up to mesh network range.

Algorithm2

Step1: take a partial mesh network which will

else {

The failure node is adjacent to the

decrease the redundancy of data.

Step2: apply DSDV routing protocol to route the packets.

Step3: colour the graph using method called chromatic graph colouring. The main reason to use this graph colouring is we can use less number of colours to colour the graph.

Step4: form table with 5 entries called destination, next Hop, metric, sequence number, colour of the node.

Step5: if any link failure occurs then the metric entry will be undetermined then we will go for 5th entry of the table in that we get colour of the node check

if(destination node colour=failure node colour){

Then the failure node is not adjacent to destination node

Then the hop count (metric) must be in between 0 to 3 find minimum distance to transfer packet by detecting node failure.

destination node through one hop count we will send the packet.

}

}

Figure: when a new node arrives towards the network.

In this diagram we know that how the net work is re-modified from the node failure.

Conclusion:

• In the existed system, they used many colors which results it increases the confusion of nodes ,to avoid this we are using Chromatic graph coloring algorithm to Schedule the packets and it uses minimum number of colors by this the confusion of node will be decreases.

• In this system we are using DSDV routing protocol to route he packets efficiently. It is a table driven protocol it contain total information about each node. And it updates it table for every 30sec.

• If a router receives new information, then it uses the latest sequence number. If the sequence number is same as the existed one, the route with the better metric is used. Stale entries are those entries that have not been updated for a while. Such entries as well as the routes using those nodes as next hops are deleted.

• In DSDV routing we get less security for this we are including SDSDV routing protocol for security purpose.

References

1. V i n o d Shokeen, Niranjan Yadav, network message communication IJECT, ISSN: 2230-7109(Online), ISSN: 2230-9543(Print)

2. Reference IEEE paper Scheduling links for heavy traffic on interfering routes in wireless mesh networks Fabio R.J.Vieira, Jose F.de Rezoned Valmir C.Barbosa, Serge fdida.

3. Simulation and protocol implementation using NS2 for wireless technology five days workshops by Tech Mahindra.

4. Andrew S.Teninbaum, Forouzan, Larry L. Peterson authors of computer networks.

5. Mesh network PDF by Raniwala, and Wikipedia. DSDV pdf by Rahman

6. Google a search engine for all information..

7. Mathematical foundation for computer science for chromatic graph colouring.