Effective Packet Management Scheme in Wireless Ad-Hoc Networks using Distributed Spanning Tree

7 pages
145 views

Please download to get full document.

View again

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Effective Packet Management(PM) is widely used in distributed environments to reduce the access costs and improve data availability. Therefore, Packet transmission in wireless environment becomes one of the important challenges for effective data transfer. This paper addresses the issues in maintaining the effective packet management in the wireless ad hoc network environments and proposes an effective solution for the same using an optimization technique. The proposed approach concentrate on local consistency issues which occurred in the network environment. Therefore, this paper evaluates the efficiency of existing techniques, and proposes a more efficient local packet management algorithm. The new algorithm leverages existing techniques which are shown to be efficient. This paper also addresses the advantages and disadvantages of various packet management and its issues.
Tags
Transcript
  Effective Packet Management Scheme in WirelessAd-Hoc Networks using Distributed Spanning Tree J. Amudhavel * M.S.Saleem Basha * T. Vengattaraman * P. Dhavachelvan * R. Baskaran #* Department of Computer Science, Pondicherry University, Puducherry, India. # Department of Computer Science and Engineering, Anna University, Chennai, India.{ amudhavel86  , smartsaleem1979, vengat.mailbox, dhavachelvan, baskaran.ramachandran}@gmail.com  Abstract  —Effective Packet Management(PM) is widely used indistributed environments to reduce the access costs and improvedata availability. Therefore, Packet transmission in wirelessenvironment becomes one of the important challenges foreffective data transfer. This paper addresses the issues inmaintaining the effective packet management in the wireless adhoc network environments and proposes an effective solution forthe same using an optimization technique. The proposedapproach concentrate on local consistency issues which occurredin the network environment. Therefore, this paper evaluates theefficiency of existing techniques, and proposes a more efficientlocal packet management algorithm. The new algorithmleverages existing techniques which are shown to be efficient.This paper also addresses the advantages and disadvantages of various packet management and its issues.   Keywords-   Packet Management, Local Packet, DistributedSpanning Tree, Wireless Application, QOS Parameters,Performance Evaluation, Ad-Hoc Networks. I.   I NTODUCTION  In the computing environment, accessing popular objectscan bring the intended items close to the clients and thereby itis possible to reduce the access latency[10] and Network traffic[17] in the distributed environments. A proper packetManagement scheme can also reduce access time and improvesfault tolerance and load balancing capabilities in order toimprove the serviceability and availability of the intendedenvironment. There are many approaches provided to solve thecritical issues in the existing filed of packet Management andthey differ in terms of their location, permanency, scope andapplicability. Based on the scope and applicability, the trafficmethods can be classified as local and global. The scope of theglobal packet Management schemes are so broad andapplicable for inter group management, whereas the localpacket Management schemes are so confined and they areapplicable for intra group management.The Local packet Management (LPM) systems areassociated with single group, where the numbers of nodes arefixed and limited. Transmission of a data item may beinconsistent in an environment where frequent data updatesoccur, particularly in case of LPM environments. Though thescope for a local group is limited, but due to the nature of thenetworks, where the nodes may be disparately placed inuncertain locations. In such environments, the enhanced degreeof serviceability and availability are essential and they can beimproved only by an effective the Local packet Managementschemes. The Propagation models suggested a procedure likethe updated version of document is to be delivered to all copiesas soon as a change is made to the document at the srcinserver. Although the copies always keep the latest version of the srcinals, this method may generate significant levels of unnecessary traffic if documents are updated more frequentlythan accessed.Y. Chang[1], addresses the interoperability issues in termsof network performance and fairness of bandwidth allocationwhen an ATM network consists of switches using different ratecontrol mechanisms, namely, the Explicit Forward CongestionIndication (EFCI) mode and the Explicit Rate (ER)mechanism. Simulation results show that these algorithms willinteroperate as long as the switch implementation conforms tothe end system.Andrea Borella[2], proposed dynamic management of DQDB Multiple Access Control. It is based on the opportuneactivation of the Increasing Counter Priority Controlledmechanism, driven by the traffic levels present at the userinterfaces. The main goal of that paper is to make the operationof the Metropolitan Area Networks clear and effective formultipriority interworking between remote computers. Theycompared the results with the results provided by a DQDBnetwork simulator.J.W.K. Hong[3] proposed the design and implementation of a portable, Web-based network traffic monitoring and analysissystem called WebTrafMon. It provides monitoring andanalysis capabilities not only for traffic loads but also fortraffic types, sources and destinations. The probe extracts rawtraffic information from the network, and the viewer providesthe user with analyzed traffic information via Web browsers.Intae Ryoo[4] proposed a new RTM (real-time trafficmanagement) scheme that can effectively manage VBR(variable bit rate) traffic having unpredictable characteristics inATM (asynchronous transfer mode) networks.In addition to its precise cell control capability, theproposed scheme intends to efficiently use the resources of high-speed, high-performance broadband networks without anydeterioration in QoS (quality of service) of the acceptedconnections.Vincenzo Catania [12] proposed the correction required bythe CAC algorithm to avoid this risk. They compare twodifferent policing mechanisms, one based on conventionallogic and another on fuzzy logic, assessing the influence of their degree of selectivity on the additional bandwidth the CACalgorithm needs to reserve in order to guarantee the QoSrequirements of all connections. Moises R. N Ribero[13] (IJCSIS) International Journal of Computer Science and Information Security,Vol. 8, No. 3, June 2010263http://sites.google.com/site/ijcsis/ISSN 1947-5500  proposed reactive method of packet management to an opticalpacket switching node.G. Chiruvolu [14] VBR video traffic that exhibits Long-Range Dependence (LRD) based on a fractional ARIMA(1,d,0) model. The Short-Range Dependent (SRD) AutoRegressive (AR) model for prediction of VBR video traffic hasalso been considered for evaluation of the proposed dynamicbandwidth allocation scheme and the performance has beencompared to that of LRD-based prediction.G. Chiruvolu [14] VBR video traffic that exhibits Long-Range Dependence (LRD) based on a fractional ARIMA(1,d,0) model. The Short-Range Dependent (SRD) AutoRegressive (AR) model for prediction of VBR video traffic hasalso been considered for evaluation of the proposed dynamicbandwidth allocation scheme and the performance has beencompared to that of LRD-based prediction.In summary, though many of the proposals dealt the issuesin the packet Management management, some of the openissues are not yet addressed; no mechanism for controlling thetime based models, no suitable model for maintaining effectivetraffic management in the network environment. Hence fromthese perspectives, in this paper, we proposed an integratedOptimal DST approach for local packet management in thenetwork environments. This model addresses the specificissues of dynamic transfer of packets management in intracircle environments.II.   P ROPOSED S YSTEM    A.    Distributed Spanning Tree The Distributed Spanning Tree (DST) [8], [15], [18] is anoverlay structure designed to allow the use of tree traversalalgorithms by avoiding the usual tree’s bottlenecks withimproved scalability. It supports the growth from a smallnumber of nodes to a large one and automatically balances theload in the intended environments. DST allows more efficientexecutions of search algorithms in term of number of sentmessages and in terms of load balancing. Though the conceptof DST has been used to simplify and optimize the floodingalgorithms and also in TTL based search algorithms, but for thepacket management there is no well defined structure toachieve the maximum utilization.A DST structure can be described with three perspectives;logical level, interconnection level and the physical level. Thelogical level is useful to understand the basics concepts of aDST and its organization. The interconnection level is used bysoftware to run a distributed tree and it is responsible of linkingthe nodes together. Finally, the physical level is the mapping of the interconnection level on a physical network layer. Here weconsidered the logical and interconnection levels for the work presented in this paper.  Logical Level: In the logical level of the DST, nodes arecalled subject. Subjects have a virtual name which has 3 digitsnumber. The nodes are organized into a hierarchy of groups.Groups are represented with dashed line rectangles. Groupsalso have a virtual name. All the elements of a group must havea unique index. The index which represents an integer that isbounded by 1 and the number of elements in the group.There is only one top level group. The subjects are puttogether to form groups of level 1. If i is not the top level, thegroups of level i are put together to form groups of level i +1.Every element of a group must know all the other elements of its group. The hierarchical structure of the DST is the same as atree where groups act as fathers and elements act as children.Interconnection Level: This is a recursive process andfinally, it is the subjects that do all the works. In theinterconnection level subjects and groups are abstract elements.Nodes are the real entities which act as subjects and groups.The DST[16] is linked by routing tables shared by all thenodes. The routing table has one row by DST level. Each rowstores the addresses of the elements of a group. But it is notpossible to have the address of a group, because groups areabstract entities in the interconnection level. Instead, it storesthe address of a node for each element of the group.  B.    Distributed spanning Trees in Message Passing The spanning tree is to be computed in a distributedmanner. This is done by attaching to every node in the graph acommunicating program that exchanges messages with theprograms at its neighbor nodes. Every program in node dmaintains two variables containing its father and the length of the minimal path found so far. In particular the state of eachprogram is uniquely determined by these program variables.Accordingly a message is a triple that can be selected bythe selector functions src ( source ), des ( destination ), lgt( length ). By a message a node src that has got information(by some message from some neighbour node) about a betterapproximation for a shortest path sends all its neighbours desthe information of the existence of a path with some length lgt.The following section describes the distributed algorithmfor constructing spanning tree:  ALGORITHM    (Distributed Spanning Tree Algorithm)Step-1: Every node sets its state to Inactive. Step-2: Construct a spanning tree, T  of the underlying unweighted graph. Any node with more than one neighbor in thetree (an interior node) must change its state to Receiving. Step-3:  Each node i determines the identities of its neighborsin G and stores identity and distance. Determine  D of thegraph G . Each node's behavior is determined by its state. Figure 1. DST Packet Transmitting Algorithm The above algorithm represents the behavior and state of the node. It determines whether the node is going to involvein which operation.   Step-4:  Transmit the final to every node from a saturatednode. Any node contains the final all pairs shortest distance.The node(s) will create a final message consisting of   D andsend this message to all its neighbors in the spanning tree T  . (IJCSIS) International Journal of Computer Science and Information Security,Vol. 8, No. 3, June 2010264http://sites.google.com/site/ijcsis/ISSN 1947-5500   Definition 1:   Let S be the proposed DST for PM providingLocal packet Management (LCM) of testing environmentconsisting of level up to 4 and it can be defined as, )2( -  1 ∑ == = nii PiS  where, ã   ‘T’ indicates the node in the Ad-Hoc Network(AHN)and ‘n’ is the number of nodes in DST in PM. ã   ‘R’ is the group formed by the interconnection betweenthe interconnection nodes and ‘n’ is the number of Representing the optimal algorithm for DSTPreliminary Group(PG) formed in the proposed DSTwhere ‘n’ is defined as n>0. ã   ‘Q’ is the Level1 Group (L1G) formed by theinterconnection between the groups and ‘n’ is the ã   number of groups formed the next level (i.e. level1) of DST where ‘n’ is defined as n>0. ã   ‘P’ is the Level2 Group (L2G) formed from theinterconnection of the level1 groups of the DST and‘n’ is the number of groups formed in the level2 of theDST where ‘n’ is defined as y>0. ã   Any node in the spanning tree that receives D willstore it locally and send D to all its tree neighborsexcept the tree neighbor which it was connected fromwhich it received D.Hence the node which passing the information or writingthe information from the other nodes are is called the LH’sof the DST. C.    Algorithm to Construct Optimal DST  The following algorithm defines the construction of optimal DST for PM in AHN. This algorithm defines how theLH’s are created and defines the way it done with theiroperations.With the above algorithm the effective DST is formed. Theefficiency of the algorithm results in efficient group formationand maintaining interconnections between the groups andnodes.In the above sections, we have seen the definition and theformation of DST using an optimal algorithm. Let us see thestep wise formation of interconnection between the nodes , andthe formation of Level Heads(HN’s).The given algorithm starts from the node creation andinitialize the distance between the two to send its packetsbetween each other. It was observed that every node has itsown characteristic properties. Figure 2. Representing the optimal algorithm for DST  Definition 2: Let R1 be the Preliminary Group (PG) for PMproviding Local packet Management (LPM) of testingenvironment and it can be defined as, )3(),......,,( :),......,,( ),......,,( ),......,,( )()()()( )()()()(3 )()()()(2 )()()()(1 1 −===== n xc xa xa x xn nk ck bk ak  x n jc jb ja j x nicibiai x T T T T  R T T T T  R T T T T  R T T T T  R  R  where, )4(.....,, )()(3 )(2)(1 − ∑∑∑∑ ============ n ya y y x xnn ya y yk  xn ya y y j xn ya y yi x T  RT  RT  RT  R  Here  xn x x x R R R R ...3,2,1 represents the collection of theindividual nodes (IN) ranging from 1 to n. In that the value of y is not constantly incremented or has any predicted values.The value is determined at the creation of the IN groups. )5()......( )()()()(1 −∪∪ = nicibiai x T T T T  R  Similarly the values for  xn x x R R R ..., 32 are calculated asdescribed as step by step below. )6(...... )()()()( −≠∪∪ φ  nicibiai T T T T   Here in the above equation 6 the collection of nodes such as )()()()( ......,, nicibiai T T T T  is not initialized to or defined to be null.Hence the value indicates the how many IN’s are formed. Sofor that reason it can be calculated to null. )7(  ....321 −=∩∩ φ   xn x x x R R R R   )1(- ),....,,,( ),....,,,( ),....,,,( ),....,,,( 4321 4321 4321 4321 = nnnn PPPPP QQQQQ  R R R R R T T T T T  S (IJCSIS) International Journal of Computer Science and Information Security,Vol. 8, No. 3, June 2010265http://sites.google.com/site/ijcsis/ISSN 1947-5500  Here in the above equation 7 the collection of PG’s such as  xn x x x R R R R ....321 ,, is calculated and the value is predictedto be null. Because no node should present in any of the PG’s if it is already present in any of the groups. Hence it is predictedto null. )8(....,, )()( )()(1 −= ∑∑∑∑ ======== n ya y y xn ya y yk n ya y y jn ya y yi T T T T  R  While representing the IN mode the PG1 is represented asthe above equation 8. When represented in the form of Groupmode The equation is represented as given below )9(  1)(1 −= ∑ == n z z z x  R R  Respectively the values of R2, R3… Rn are calculated andthe overall equation is written as follows, )10(........,, 1)(1)(31)(21)(1 −==== ∑∑∑∑ ======== n z z z xnn z z z xn z z z xn z z z x R R R R R R R R  where Ri,R2,Ri.. Rn are the Preliminary Groups(PG)formed by the DST where m is defined as m>0&&m<w.Here in equation (2) the value of Rx1 is by the PG formedby individual interconnected nodes ),......,,( )()()()( nicibiai T T T T  . Consecutively same applicablefor Rx2, R3 and so on. Here PG is formed from the individualnon-interconnected nodes which are free from any bindings.So by interconnection the nodes the PG such as Rx2, Rx3, Rx4,Rx5 and so on. The PG is formed randomly without any rules.While in the formation of the preliminary groups the no of nodes which forms a group is not a constraint. It should formon their own. Figure 3. Step by Step group formations and interconnections between thegroups and nodes in Wireless AHN The interconnection of the nodes is done by various factorslike read operation, replying relativity, access rate etc. Herbelow equation no (3),(4),(5),(6),(7),(8) representing theformation of PG with the individual nodes. (9) and (10)represents the final formation of PG.The set of all data items is denoted by T, where n is thetotal number of nodes of the group formed in the Step1. Here iranges from 1 to n.Now, after the formation of (L1G) which it was formed bythe PG’s they had interconnection between themselves andform the superior group. Following the same principle, all the(L1N’s) are interconnected and form the superior group[17] of what they are concerned with. The formation of the (L1N’s)are explained in the above Figure.2  Definition 3: Let Q1 be the Level1 Group (L1G) for PMproviding Local packet Management (LCM) of testingenvironment and it can be defined as, )11(),......,,( :),......,,( ),......,,( ),......,,( )()()()( )()()()(3 )()()()(2 )()()()(1 1 −===== n xc xa xa x xn nk ck bk ak  x n jc jb ja j x nicibiai x  R R R RQ  R R R RQ  R R R RQ  R R R RQ Q  where, )12(.....,, )()(3 )(2)(1 − ∑∑∑∑ ============ n ya y y x xnn ya y yk  xn ya y y j xn ya y yi x RQ RQ RQ RQ  Here  xn x x x QQQQ ...3,2,1 represents the collection of thePG’s ranging from 1 to n. In that the value of y is notconstantly incremented or has any predicted values. The valueis determined at the creation of the IN groups. )13()......( )()()()(1 −∪∪ = nicibiai x R R R RQ  Similarly the values for  xn x x QQQ ..., 32 are calculated asdescribed as step by step below. )14(...... )()()()( −≠∪∪ φ  nicibiai R R R R  Here in the above equation 14 the collection of nodes suchas )()()()( ......,, nicibiai R R R R is not initialized to ordefined to be null. Hence the value indicates the how manyPG’s are formed. So for that reason it can be calculated to null. )15( ....321 −=∩∩ φ   xn x x x QQQQ  Here in the above equation 15 the collection of L1G’s suchas  xn x x x QQQQ ....321 ,, is calculated and the value ispredicted to be null. Because no PG’s should present in any of the L1G’s if it is already present in any of the groups. Hence itis predicted to null. )16(....,, )()( )()(1 −= ∑∑∑∑ ======== n ya y y xn ya y yk n ya y y jn ya y yi R R R RQ  While representing the PG mode the L1G is represented asthe above equation 16. When represented in the form of Groupmode the equation is represented as given below (IJCSIS) International Journal of Computer Science and Information Security,Vol. 8, No. 3, June 2010266http://sites.google.com/site/ijcsis/ISSN 1947-5500
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x