A New Scheme for Packet Exchange in Wireless Ad-Hoc Networks

A New Scheme for Packet Exchange in Wireless Ad-Hoc Networks

1Shermimol Hanifa, 2 Vipin Thomas

Department of Electronics and Communication Engineering Ilahia College of Engineering & Technology, Muvattupuzha

Abstract- In data networking and queueing theory, network congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include queueing delay,packet loss or the blocking of new connections. A consequence of these latter two is that incremental increases in offered load lead either only to small increases in network throughput, or to an actual reduction in network throughput. A distributed adaptive opportunistic routing scheme for wireless networks was proposed earlier. But it cannot be able to control the congestion. we are introducing a new scheme for packet exchange in wireless sensor networks by reducing the number of acknowledgements in the networks.

keywords : Opportunistic Routing,Routing Algorithm, Reward Maximization,Wireless ad-hoc networks.

1. INTRODUCTION

   A wireless ad hoc network is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre existing infrastructure, such as routers in wired networks or access points in managed wireless networks. Instead, each node participates in routing by forwarding data for other nodes, so the determination of which nodes forward data is made dynamically on the basis of network connectivity. In addition to the classic routing, ad hoc networks can use flooding for forwarding the data.

   An ad hoc network(fig 1) typically refers to any set of networks where all devices have equal status on a network and are free to associate with any other ad hoc network device in link range. Ad hoc network often refers to a mode of operation of IEEE 802.11 wireless networks.

   Opportunistic routing for multi-hop wireless ad-hoc networks has seen recent research interest to overcome deficiencies of conventional routing [1][6] as applied in wireless setting. Motivated by classical routing solutions in the Internet, conventional routing attempts to find a fixed path along which the packets are forwarded [7]. Such fixed path schemes fail to take advantages of broadcast nature and opportunities provided by the wireless medium and result in unnecessary packet retransmissions. The opportunistic routing decisions, in contrast, are made in an online manner by choosing the next relay based on the actual transmission outcomes as well as a rank ordering of neighboring nodes. Opportunistic routing mitigates the

   impact of poor wireless links by exploiting the broadcast nature of wireless transmissions and the path diversity.

   The authors in [1] and [6] provided a Markov decision theoretic formulation for opportunistic routing. In particular, it is shown that the optimal routing decision at any epoch is to select the next relay node based on an index summarizing the expected-cost-to-forward from that node to the destination. This index is shown to be computable in a distributed manner and with low complexity using the probabilistic description of wireless links. The study in [1], [6] provided a unifying framework for almost all versions of opportunistic routing such as SDF [2], Geographic Routing and Forwarding (GeRaF) [3], and EXOR [4]. The variations in [2][4] are due to the authors choices of cost measures to optimize.

   Fig 1.wireless ad-hoc network

   The opportunistic algorithms proposed in [1][6] depend on a precise probabilistic model of wireless connections and local topology of the network. In practical setting, however, these probabilistic models have to be learned and maintained. In other words, a comprehensive study and evaluation of any opportunistic routing scheme requires an integrated approach to the issue of probability estimation. Authors in [8] provide a sensitivity analysis in which the performance of opportunistic routing algorithms are shown to be robust to small estimation errors. However, by and large, the question of learning/estimating channel statistics in conjunction with routing remains unexplored.

   In this paper, we also investigate the problem of opportunistically routing packets in a wireless multi hop network when zero or erroneous knowledge of transmission success probabilities and network topology is available. Using a reinforcement learning framework, proposed an adaptive opportunistic routing algorithm which minimizes the expected average per packet cost for

   routing a packet from a source node to a destination. Our proposed reinforcement learning framework allows for a low complexity, low overhead, distributed asynchronous implementation.

   The idea of reinforcement learning has been previously investigated for conventional routing in Ad-hoc networks

   [9] [10]. In [9], a ticket-based probing scheme is proposed for path discovery in MANETs to reduce probe message overhead. This heuristic can be viewed as a very special case of our work where the probabilistic wireless link model is replaced with a deterministic link model. In [10], the authors attempts to find an optimal path dynamically in response to variations in congestion levels in various parts of the network. As discussed in the conclusion, the issue of congestion control remains open and entails further research.

   The rest of the paper is organized as follows: In Section II, we discuss about opportunistic routing networks. Section III , we present the implementation details and practical issues. We perform simulation study of the proposed system. Finally, we conclude the paper and discuss future work in Section IV.

2. OPPORTUNISTIC ROUTING

   A.Opportunistc networks

   In many MANET application environments, nodes form a Disconnected networks due to nodal mobility, node sparseness, lossy link of signal attenuation or shut down the transmission to conserve energy and etc. Traditional MANET and Internet routing/forwarding techniques are not available because they implicitly assume that the network, even if sparse, is connected (or can be made by

   e.g. tuning transmitting powers) and an end-to-end path always exists between any source-destination.

   Constitute the category of ad hoc networks where diverse systems, not originally employed as components, join in dynamically to exploit the resources of separate networks according to the needs of specific application tasks. Communication Opportunities (contact) are intermittent.

   Network is partitioned & No continuos end-to-end path.

   In routing phenomena the data packets are successfully routing from the source node to the destination node without any delay. A successfull routing pattern of an opportunistic routing network is shown in fig.2.A node which is considered as the source node S, which will transmit the data packets to the neighbouring node, so on, finally the data packets reached destination node D and send acknowledgement back to the source node.

   The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. We define the termination event for packet to be the event that packet is either received by the destination or is dropped by a relay before reaching the destination. The routing decision at

   any given time is made based on the successful outcomes and involves retransmission, choosing the next relay, or termination.

   Fig.2 Opportunistic routing network basic structure

   1. outing algorithm

      As discussed before, the routingdecision at any given time is made based on the successful outcomes and involves retransmission, choosing the next relay, or termination. Our proposed scheme makes such decisions in a distributed manner via the following three-way handshake between node i and its neighbors N(i).

      1. At time n node i transmits a packet.

      2. Set of nodes who have successfully received the packet from node i, transmit acknowledgment (ACK) packets to node i. In addition to the nodes identity, the acknowledgment packet of node includes a control message known as estimated best score (EBS) .

      3. Node i announces node as the next transmitter

   or announces the termination decision f in a forwarding(FO) packet.

   The algorithm used is adaptive opportunistic routing algorithm. The data packets are routed to the nodes even in the absence of reliable knowledge about channel statistics and network model. This routing scheme jointly addresses the issues of earning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities.

   The operation of routing algorithm can be described in terms of initialization and four stages of transmission, reception and acknowledgment, relay, and adaptive computation as shown in Fig.3. For simplicity of presentation we assume a sequential timing for each of the stages.

   the node N0(source) after the date packet is successfully reached at the node N2, and next to the node N3(destination).

   Fig.4 node transmission and acknowledgement passing

   Fig.3 Flow of the algorithm

   Initialization:

   Initializing all the number of nodes in the network. In this paper we are using 26 nodes. In initialization stage initializing all the 26 nodes.

   Transmission Stage:

   Transmission stage occurs at time n in which node i transmits if it has a packet.

   Reception and Acknowledgment Stage:

   The set of neighbouring nodes that have received the packet transmitted by node i. In the reception and acknowledgment stage, successful reception of the packet transmitted by node i is acknowledged to it by all the nodes in. We assume that the delay for the acknowledgment stage is small enough (not more than the duration of the time slot) such that node i infers by time n+.

   Relay Stage:

   Node i selects a routing action in according with the EBS value received. Node i transmits FO, a control packet which contains information about routing decision.

   Adaptive Computation Stage:

   After being done with transmission and relaying, node i updates score vector for the further routing.

   As we seen before by using adaptive opportunistic routing algorithm the routing of data packets are successfully achieved even in the absence of reliable knowledge about the channel statistics and network model. The data packets will send to the nearest neighbour without knowing the channel statistics and network model. By using this algorithm we cannot reduce or control congestion occurred in the network In the case of opportunistic routing algorithm, consider the nodes N0(source),N1,N2,N3 shown in the fig4. when a data packet is send from node n1 to node N2,an acknowledgement is send back to the node N1 and also to

   From the fig 4 it is well known that increasing the number of acknowledgements leads to congestion in the network. In order to overcome the congestion problem we are reducing the number of acknowledgements. so we are proposing a new scheme for packet exchange in wireless ad-hoc network by reducing the number of acknowledgements to control the congestion in the network.

   Fig5. Node transmission and acknowledgement passing(proposed)

   The node transmission and acknowledgement passing by using the proposed scheme is shown in the fig 5.by reducing the nuber of acknowledgemsnts in the existing scheme we can able able to control the congestion in the overall network.

3. IMPLEMENTATION DETAILS

   The proposed paper is implemented by using network simulator (NS2). A package of tools that simulates the behavior of networks. It will Create Network Topologies (nodes,links), log events that happen under any load, analyze events to understand the network behavior (NAM). Network Animator (NAM) is a visual aid showing how packets flow along the network.

   The simulation result of the proposed scheme is shown in the fig6. The data packets are successfully received at the destination without causing any delay. we are proposing a new scheme for packet exchange in wireless

   ad-hoc network by reducing the number of acknowledgements in the adaptive routing scheme to control the congestion in the wireless ad-hoc network.

   (a)

   (b)

   (c)

   (d)

   Fig6.(a). initializing source node and sink node, (b). packet received at the set of nodes, (c). node transmission and message passing, (d). packet received at the sink node.

4. CONCLUSIONS

In this paper, we proposed a new scheme for packet exchange in wireless ad-hoc networks which maximizes the expected average per packet reward from a source to a destination by control the congestion in the wireless ad- hoc networks by reducing the number of acknowledgements. The scheme allows for a practical distributed implementation with provably optimal performance under idealized assumptions on stationarity of network and reliability of acknowledgment scheme. The performance of the proposed scheme is also investigated in practical settings via simulations. Simulation results show that the proposed scheme outperforms the existing opportunistic protocols in which statistical link qualities are empirically built and the routing decisions are greedily adapted to the empirical link models. The proposed reinforcement learning framework allows for a low complexity, low overhead, distributed asynchronous implementation. An important area of future work comprises of developing fast converging algorithms which optimize the regret as a performance measure of interest.

REFERENCES

1. A.A. Bhorkar, M. Naghshvar, T. Javidi, Member, and

   B.D. Rao, Fellow, An Adaptive Opportunistic Routing Scheme For Wireless Ad-hoc Networks,IEEE 2009 June 9.

2. C. Lott and D. Teneketzis, Stochastic Routing in Ad hoc Wireless Networks, Decision and Control, 2000. Proceedings of the 39th IEEE Conference on, vol. 3, pp. 23022307 vol.3, 2000.

3. P. Larsson, Selection Diversity Forwarding in a Multihop Packet Radio Network with Fading channel and Capture, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 2, no. 4, pp. 4754, October 2001.

4. M. Zorzi and R. R. Rao, Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Multihop Performance, IEEE Transactions on Mobile Computing, vol. 2, no. 4, 2003.

5. S. Biswas and R. Morris, ExOR: Opportunistic Multi hop Routing for Wireless Networks, ACM SIGCOMM Computer Communication Review, vol. 35, pp. 3344, October 2005.

6. S.R. Das S. Jain, Exploiting Path Diversity in the Link Layer in Wireless Ad hoc Networks, World of Wireless Mobile and Multimedia Networks, 2005. WoWMoM 2005. Sixth IEEE International Symposium on a, pp. 2230, June 2005.

7. C. Lott and D. Teneketzis, Stochastic Routing in Ad hoc Networks, IEEE Transactions on Automatic Control, vol. 51, pp. 5272, January 2006.

8. E. M. Royer and C.K. Toh, A Review of Current Routing Protocols for Ad-hoc Mobile Wireless Networks,

   IEEE Pers. Communications, vol. 6, pp. 4655, April 1999.

9. T. Javidi and D. Teneketzis, Sensitivity Analysis for Optimal Routing in Wireless Ad Hoc Networks in Presence of Error in Channel Quality Estimation, IEEE Transactions on Automatic Control, pp. 13031316, August 2004.

10. W. Usahaa and J. Barria, A Reinforcement Learning Ticket-Based Probing Path Discovery Scheme for MANETs , Elsevier Ad Hoc Networks, vol. 2, April 2004.