Localized Scheduling For Dense Wireless
Networks Using CSMA Algorithm

M. Rajeshwaran; M. Suguna; D. Sharmila

Localized Scheduling For Dense Wireless Networks Using CSMA Algorithm

M. Rajeshwaran¹, M. Suguna², D. Sharmila³

PG student, Dept of Information Technology, SNS College of Technology, Coimbatore, India
Associate professor, Dept of Information Technology, SNS College of Technology, Coimbatore, India
Head, Dept of Electronics and Instrumentation Engineering, Bannari Amman Institute of Technology, sathiyamangalam, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

The network throughput will changed when network size modified and it will specified by capacity scaling property. It provide the essential performance in dense wireless networks. Existing result have been obtained based on the scheduling partition scheme and this methodology not feasible in dense wireless networks due to the scheduling complexity, packet loss, time delay. In this paper we implement the connection level scheduling in wireless networks using only MAC layer information and to improve the throughput optimal scheduling performance when files are arrival and dispatcher. The scheduler has access the total queue length at MAC layer then it will use max weight scheduling algorithm to achieve the throughput and concentrate the CSMA scheduling algorithm, it will implemented in decentralized way. CSMA indeed achieve throughput optimality without the timescale separation assumption. Finally connection level scheduling achieve throughput even use only MAC layer queue length information.

Keywords

network capacity, scheduling partition, distributed partition protocol, localized scheduling algorithm, max weight scheduling algorithm, csma algorithm

INTRODUCTION

To operate the dense wireless network efficiently, the capacity scaling and scheduling algorithm needed to maintain the concurrent transmission between different users. Wireless interference and multihop relay prevent a large wireless mesh from high throughput. The throughput capacity of the dense wireless network has obtain substantial attention in past few years. Figure 1.1 discribe the structure of the wireless network. Here number of systems connect via wireless link.

The thoughtful link scheduling can assurance certain grades of conduit utilization such that the achievable throughput is a constant part of the top bound. The work in advised initially from the throughput of unicast communication later implement with broadcast communication and finally end with multicast communication. Another important breakthrough on dense wireless mesh throughput capacity was made by utilizing the percolation procedure, used to improve the unicast and multicast capacity bounds when nodes randomly placed in mesh. All the results are obtained by existing scheduling algorithms are may not feasible in dense wireless network.

Figure 1.1 wireless Network structure

The aim of these studies is to maximize the mesh throughput while double-checking every transmission to be thriving. The centralized design collect the whole mesh the whole mesh topology data to compute a collision free schedule but its not suitable when network size increased. The circulated arranging algorithm work better in dense network and not for assembling international topologies. The amount of exchanged nodes and the latency to work out the transmission agenda boost as mesh dimensions arguments. In addition to scheduling random access to has been studied in the literature as a alternative approach. Using random access method transmission collisions are occur so it cannot accomplish the maximal network. So reduce the collision in dense network have improved the throughput to maximize by taking up the carrier sense multiple access technique and adapting the random access likelihood according to the traffic burden. The literature result of the random access designs supply simple and effective connection transmission solutions in wireless systems. So next go to study a new approach distinct from the random access to solve the wireless transmission problems.

In this paper we suggest a scheduling partition methodology to address the feasibility of greatest capability climbing in dense wireless networks. It decay the dense wireless network into number of small independent nodes then apply the scheduling algorithm to schedule broadcast in each partition node. Since it is not optimized and possible to collision occur. So in this paper the parallel routing based on percolation theory and schedule respectively short-hops and long-hops is implemented. In the other type, the routing without using the percolation theory in order to avoid the bottleneck on the accessing path into highways Combining with the two types of schemes, obtain the achievable throughput as the lower bounds of multicast capacity.

Fig 1.2 gives the details about the architecture of our system. First construct the network using deployment of nodes in the area. Then form a routing using adhoc ondemand distance vector routing (AODV). After that want to partition the large network into small independent area. Then establish the connection between partitions area using localized scheduling algorithm. Finally use the parallel scheduling algorithm in the case of to achieve efficient throughput. Efficient operation of wireless networks has always been a crucial task due to the inherentbroadcast nature of the wireless medium.

Figure 1.2 system architecture

The rest of this paper structured as follows: first describe the network model in section 2 . In section 3 explain the design of distributed partition protocol and describe the localized scheduling algorithm and parallel scheduling algorithm in section 4. Next describe the future work in section 5. And finally give the conclusion in section 6.

Network Model

A kind of network forms have been utilized in the literature to comprise different scenarios of node expansions, node communication, position distribution and interferences. A usually applicable arranging method, consider all these forms in this paper. And the network model is based on the extended network model. It also consider the following model based on the above parameters.

The expanted network is distinguished by n nodes circulated in rectangle district B with localality B=n. As mesh scales the node density holds unchanging 1. After including this scaling component our outcome in this paper further more addredd the following forms for wireless interferences, node location and communication scenarios.

In the interference model use three models they are protocol model, generalized physical model, physical model. In the location model address two prevailing node position models random and random mesh. In random systems node locations are circulated in a random poisson issue process and the random mesh model represent a node positions are allotted in need. And finally communication module use the unicast, multicast, broadcast technique.

There are two possible notions of connectivity for a dense network. The first considers only the topology of the connectivity graph that can be derived from the dense network. The second is a more stringent condition that also considers contention issues in the network. The existing results use the first definition, which is the tradition that will be continued, to explain most of the parts, however some heuristics for addressing the second requirement of connectivity are also presented. The goal of connectivity can be summarized as follows. Assume that n sensors are deployed in area. Let rS be the sensing radius and rT be the transmission radius. Suppose a sensing event fires at some position x ε T and it is to be transmitted to y ε T. It is very important to successfully transmit the occurrence of an event with high probability for any x, y.

Modules Implementation

This paper contain totally five modules. There are network construction, pocket routing, network partition module, localized scheduling module, parallel scheduling module. In the first module want to construct the more number of nodes, set the direction, coverage area, antenna type etc. After that perform the routing using AODV routing protocol. It is a on demand routing protocol. Main advantage of this algorithm is destination sequence number, using that easily find out the path when pathloss or connection broken will occur. The network partition module split the entire network into more number of small network. The sink node will act as a cluster head to communicate with other sink nodes. The information of the sub nodes of the networks will passes via the sink node. After that communicate the sink node using the localized scheduling module. In this module the link will be generated and connect the networks. The parallel scheduling will find the alternative paths when the packet data send to out of the transmission range.

Design of Scheduling Partition Protocol

A. Distributed Partition Protocol

The dimensions of each partition should be at smallest propotional to the critical transmission radius. As desire the maximum node capability and minimize the scheduling overhead simultaneously , finally develop the least significant acceptable partitions to minimize the protocol overhead.

Specifically partition localities should be enclosed between an inner computer disk of radius. Note that when the percolation main road system is utilized for routing in the random node position model to get access to and exit. In this case need the partition dimension to be on the alignment of log np such that the partition dimensions obligation holds by utilizing voronoi Tessellation our task is in fact to work out the subset of nodes that will serve as the schedulers. The non scheduler nodes simply connect the respective closest schedulers to form partitions. The basic concept of this distributed partition protocol is the scheduler conclusion by random affray. Each node in the network volunteers to become a scheduler with some selfrecommendation likelihood. If two nodes that are close to each other assertion to be schedulers simultaneously. One gives up the affray such that the developed partitions will conform to the dimensions obligation.

The partition method finishes when every node belongs to a partition. Note that there is a tradeoff between the partition overhead and the convergence time that is controlled by the self-recommendation probability. For a higher probability, larger overhead and much quicker convergence are anticipated. So configure this likelihood to be inversely proportional to the node density, which double checks that both the overhead and the convergence are with acceptable bounds.. This protocol runs in every node individually until the node has very resolute to become a scheduler or it has chosen a nearby scheduler to join. According to the protocol, the undecided nodes first exchange their identification and position data.

The protocol structure contain the following steps

1.Source node send the broadcast message to the destination via neighbour nodes.

2.Determine the node set Ni.

3.Choose the scheduler node with have probability 1/aNi and set the backoff timer.

4.Before expire backoff timer the scheduler announce the status with in particular distance.

5.If there is no scheduler is available means repeat the above steps.

B. Localized Scheduling Algorithm

The localized scheduling algorithm runs in each scheduling partition and in each time slot t.

The algorithm contain the following steps

1.A set of links that is going to requesting transmission was given as a input.

2.Then it will select a link randomly from a whole network link.

3.Also the link satisfy the main result that is the scheduling will have a minimum interspace, and partition size is a convex polygon , finally at any time any location atleast one link must be scheduled for transmission.

Since it is not feasibility in dense wireless networks due to the time delay , packet loss, collision. So implement the parallel scheduling algorithm in this paper.

PARALLEL SCHEDULING ALGORITHM

The performance of these parallel scheduling algorithm depends on the circulation of the nodes across the levels. And it will support for the node based scheduling and level based scheduling. The parallel scheduling algorithm is also based on the distributed scheduling algorithm so surely it will support the dense wireless network. A proper schedule not only avoid collisions of every receiver node in each time slot and also minimize the number of time slots, latency. The more or high time slots will increase the data rate. More than one node can exchange data at the same time if their destinations are non conflicts parts of the network. Here the conflicts are two types they are primary and secondary conflict. A primary conflict occurs when a node deliver more number of transmission at the same time or the destination receive more data same time with in a particular transmission range. The secondary conflict occur when a node plan to receive of a particular transmission.

The algorithm have the following steps

Step 1: The number of partition nodes are given as a input.

Step 2: Then transmission is begin.

Step 3: while atleast one packet has not reached the destination for with in a time for s= 1 to M.

Step 4: After that define sets = set of nodes corresponding to transmission range with at least one packet.

Step 5: T =sets , set of nodes not corresponding to transmission range s with at least one packet.

Step 6: finally update the place of packet and end

SIMULATION RESULT

In the network simulations, the transmission time of all links is exponentially distributed with mean 1ms, and the backoff time of link k is exponentially distributed with mean 1/ exp(rk)ms. So the capacity of each link is 1(data unit)/ms. In the starting period, all queues are empty, and the initial value of rk is 0 for all k.

Figure 5.1 Throughput comparision graph

The fig5.1 throughput comparision result graph show that the proposed algorihm that is localized scheduling partition with parallel scheduling is working better than the existing work . here the graph ploted between the number of nodes in the network and throughput of the network.

CONCLUSION AND FUTURE WORK

In the present work the scheduling partition in dense wireless networks using Parallel Scheduling algorithm is implemented. It will be used to achieve the throughput interms of packetloss. Using this algorithm first partition the network into small number of independent partition area. Then connect the partition area using scheduling algorithm. Parallel scheduling algorithm used to find out the parallel paths among the network. So when a packet loss or traffic occur it will manage the packet loss using alternative paths. Finally we show that our algorithm achieve maximum throughput than existing.

In future work, a new scheduling Partition schemes called Max-weight and CSMA algorithm which is to find out to achieve the throughput more effectively . It will be performed at the MAC layer. Because scheduling is the part of the MAC. The source need a distributed MediumAccess Control (MAC) protocol to determine which users should transmit which makes the efficient operation even complex situation. The main advantage of this algorithm is short file transmission is not blocked by the long file transmission. Both Max-weight and CSMA algorithm is a distributed algorithm, so each and every node will have the responsibility to know the own MAC information and its carrier sensing information. CSMA (Carrier sense Multiple access) type protocols are an important class of MAC protocols due to their simplicity of implementation, and have been widely used in real time. For example in WLANs (IEEE 802.11 Wi-Fi) or emerging wireless mesh networks. Using this protocols, each user listens to the channel and can transmit, with some probability, only when the channel is not busy. Even the extreme simplicity of the CSMA-type algorithms, their efficiency have been always questionable.

References

Didem Gozupek, Seyed Buhari, an Fatih Alagoz “A Spectrum Switching Delay-Aware Scheduling Algorithm for Centralized Cognitive Radio Networks” IEEE Transaction on Mobile Computing, VOL. 12, No. 7, July 2013 pp 1270-1280.
Li, Shi Liu, Yunhao Li, Xiang-Yang, “Capacity of Large Scale Wireless Networks Under Gaussian Channel Model” MOBICOM'08, . 2008, Sep, p.140-151.
Yaqin Zhou, Xiangyang Li, Min Liu, Xufei Mao, Shaojie Tang, Zhongcheng Li “Throughput Optimizing Localized Link Scheduling for Multihop Wireless Networks Under Physical Interference Model”, arxiv 1301.4738v2 21 Jan 2013 (v1)
Y. Xu and W. Wang, “Scheduling Partition for Order Optimal Capacity in Large Scale Wireless Networks,” Proc. ACM MobiCom, Sept. 2009, pp 109-120
Marco Fiore, Claudio Ettore Casetti, Carla-Fabiana Chiasserini, and Panagiotis Papadimitratos, “Discovery and Verification of Neighbor Positions in Mobile Ad Hoc Networks” IEEE Transaction on Mobile Computing, Vol. 12, No. 2, Feb 2013 pp289-303
Nidal Nasser, Lutful Karim, and Tarik Taleb “ Dynamic Multilevel Priority Packet Scheduling Scheme for Wireless Sensor Networks” IEEE Transaction on Wireless Communication, Vol. 12, No. 4, April 2013 pp 1448-1459
Jiajia Liu, Xiaohong Jiang,Hiroki Nishiyama, and Nei Kato, “Throughput Capacity of MANETs with Power Control and Packet Redundancy” IEEE Transaction on Wireless Communication, Vol. 12, No. 6, JUNE 2013 pp 3035-3048
Libin Jiang and Jean Walrand “A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks” sep 2008, pp 1511-1519
Matthew Andrew, Kyomin Jung, Alexander Stolyar “Stability of the Max Weight Routing and Scheduling Protocol in Dynamic Networks” STOC’07, June 11–13, 2007
Xin Ming Zhang, En Bo Wang, Jing Jing Xia, and Dan Keun Sung “A Neighbor Coverage-Based Probabilistic Rebroadcast for Reducing Routing Overhead in Mobile Ad Hoc Networks” IEEE Transaction on Mobile Computing, Vol. 12, 2013 pp1-10