Performance Evaluation of Global and Local Optimization of Wireless Nodes

Performance Evaluation of Global and Local Optimization of Wireless Nodes

S. Revathi K. Aravind Kumar

M.E Scholar Assistant professor

Department of computer science and engineering Department of Computer Science and Engineering Manonmaniam Sundaranar University Manonmaniam Sundaranar University Tirunelveli- 627012, India Tirunelveli-627012, India

Abstract–Perform the global and local optimization in wireless network, where a set of information dissemination devices (IDDs) broadcast a limited amount of location-based information to passing mobile nodes that are moving along well-defined paths. Develop a novel model that captures the main aspects of the problem and define a new optimization problem called as Maximum Benefit Message Assignment Problem (MBMAP).Develop new approximation algorithms for these variants and then focus on the practical effects of using them in realistic networking scenarios. To avoid the network deployment and to be perform the structure analysis.

Index termsoptimization problem, structure analysis, avoid network deployment.

1. INTRODUCTION

   An important field of network optimization problems is related to Network Design problems, where given a set of nodes of the graph (called terminals) that want to communicate with each other, and need to buy some edges of the graph to connect all the terminals. They can be classified at two type of optimization.

   • Local optimum: A solution to a problem that is better than all other solutions that are slightly different, but worse than the global optimum.

   • Global optimum: Global optimization is the task of finding the absolutely best set of parameters to optimize an objective function. In general, there can solutions that are locally optimal but not globally optimal.

   For the modeling of military assets, group mobility models have drawn a lot of interest recently. The mobility models proposed so far in the literature assume some kind of permanent group affiliation. Also they require that each node belongs to a single group. In reality in a typical military scenario, a much more complex mobility behavior is observed. mobility of the nodes are in groups; while others move individually and independently; a fraction of nodes are static. Moreover, the group affiliation is not permanent. The mobile groups can dynamically re-configure themselves triggering

   group split and mergence. All these different mobility behaviors coexist in military scenarios.

2. MBMAP

   MBMAP means Maximum Benefit Message Assignment Problem. One of the optimization problem. MBMAP can be solved with or without cooperation among the IDDs. When cooperation between the IDDs is possible, these version of MBMAP is Global MBMAP (G-MBMAP).

   When there is no cooperation, every IDD makes a local decision regarding the most important information to broadcast to the flows, these version of MBMAP is Local MBMAP (L-MBMAP).

3. RELATED WORK

   Group and swarm mobility model [5], node mobility is one of the inherent characteristics of mobile ad hoc networks (MANET). It is also one of the parameters that most critically affect the performance of network protocols (e.g., routing). Today, in most simulation experiments, node movement is modeled as an independent random walk. One such model is the Random Way Point Mobility (RWP) model, which is the most popular mobility model used in the literature. However, in real military scenarios, node mobility is not always independent. Mobility correlation among nodes is quite common. One typical example is group mobility. In the battle field, nodes with the same mission usually move in groups such as UAV swarms or tank battalions. The Random Walk Mobility Model described in another popular random mobility model. In this model, each node selects a direction in which to move from the range [0…2].

   Generalized Maximum Coverage Problem (GMC) [6], Its one of the new maximization problem, its contains the Maximum Coverage Problem, Budget Maximum Coverage Problem, Generalized Maximum Coverage. GMC is an extension of the Budgeted Maximum Coverage Problem, and it has important applications in wireless OFDMA scheduling.

   The greedy algorithm presented in for MC(Maximum Coverage Problem) has L iterations ie,number of input iterations. During every iteration, this algorithm picks the

   most profit table subset of elements in C from the not-yet- selected elements.

   An (e/e-1)-approximation algorithm, equivalent approach for BMC is to pick the highest density bin with respect to the set of not-yet-selected elements, until no bin can be added without violating the budget constraint. However, as shown in such an algorithm has no worst-case approximation guarantee. It is also proven that a variation of this algorithm, which returns as a solution either the most profit table bin or the

   greedy solution, yields a ( 1)-approximation algorithm

   for BMC. In this paper we use a similar approach for GMC, which achieves a (2e/e-1+)-approximation1 algorithm guarantee.

   Group Mobility model [3], Survey of various mobility models in both cellular networks and multi-hop networks. Group motion occurs frequently in ad hoc networks, and introduces a novel group mobility model Reference Point Group Mobility (RPGM) – to represent the relationship among mobile hosts. RPGM can be readily applied to many existing applications. RPGM model to two different network protocol scenarios, clustering and routing, and have evaluated network performance under different mobility patterns and for different protocol implementations.

   As expected, the results indicate that different mobility patterns affect the various protocols in different ways.

   In a wireless network, Mobile Hosts (MHs) can move in many different ways. Mobility models are commonly used to analyze newly designed systems or protocols in both cellular and ad hoc wireless networks.

   In cellular wireless networks, studies for mobility models not only aim at describing individual motion behaviors such as changes in direction and speed, but also consider the collective motion of all the mobiles relative to a geographical area (cell) over time. Models for ad hoc network mobility generally reflect the behavior of an individual mobile, or a group of mobiles. Routing algorithms is influenced by the choice of mobility pattern.

4. IMPLEMENTATION METHODOLOGY

   1. MBMAP

      It is clear that in general the global algorithms perform better than the local algorithms, our main purpose in this section is two field:first, to study the effect of the extended model on the performance; second, to better understand the effect of some network parameters on each of the various models and algorithms

      Fig 4.1 overall design architecture of implementation methodology

      One of the optimization problems is referred to as Maximum Benefit Message Assignment Problem (MBMAP). MBMAP can be solved with or without cooperation among the (Information dissemination devices ) IDDs. When there is no cooperation, every IDD makes a local decision regarding the most important information to broadcast to the flows.

      This version of MBMAP is referred to as fig 4.1 local MBMAP (l-MBMAP), and its most important property is that no communication infrastructure is needed between the IDDs. Cooperation between the IDDs is possible, a global decision can be made while taking into account the fact that flows pass through several IDDs. This version of MBMAP is referred to as global MBMAP (g-MBMAP). It is easy to see that the best solution for l-MBMAP ca never be better than the best solution for g-MBMAP.

      Extend MBMAP to the case where the different messages are correlated. In this case, distinguish between two variants: local extended MBMAP (l-E-MBMAP) and global extended MBMAP (g-E-MBMAP).

   2. Global and local MBMAP

      MBMAP can be solved with or without cooperation among the IDDs. When there is no cooperation, every IDD makes a local decision regarding the most important information to broadcast to the flows. This version of MBMAP is referred to as local MBMAP (l-MBMAP), and its most important property is that no communication infrastructure is needed between the IDDs. This property is important, for instance, when the IDDs are sensors it to be performed the sensor network.

      When cooperation between the IDDs is possible, a global decision can be made while taking into account the fact that flows pass through several IDDs. This version of MBMAP is referred to as global MBMAP (g-MBMAP). It is easy to see that the best solution for l-MBMAP can never be better than the best solution for g-MBMAP. However, the improved performance of g-MBMAP comes at the cost of coordinating the broadcast of different IDDs, which requires a centralized management entity and a communication infrastructure that connects the IDDs.There are two important differences between g-MBMAP and GAP.

      • In GAP, every item can be selected only for one bin, whereas in g-MBMAP, an item (a message) can be selected for multiple bins (IDDs).

      • In GAP, the benefit associated with the selection of an item for a bin is independent of the selection made for other bins. In contrast, in g-MBMAP there is a strong correlation between assignments. As explained before, if a message is selected for multiple IDDs and the same flow passes through certain nodes, the benefit this flow obtains from this message is not equal to the sum of the benefits, but to the maximum benefit.

   3. Extended MBMAP

   Extend MBMAP to capture possible dependency between different messages and define two new problems: G-E- MBMAP and L-E-MBMAP.

   Each flow has a benefit from being notified about every event in every message. For example, if a flow is notified about the same event by two different IDDs, it obtains only the maximum benefit associated with this event and the two IDDs.

   G-E-MBMAP solve to use BMCP as a subroutine. ALG be a -approximation algorithm for GBMCP. It will be extended to the global MBMAP.G-MBMAP transfer the message based

   1))+e)approximation for every e>0 . In this variation, not only does the benefit of the element differ from one subset to another, but also its weight

5. APPROXIMATION ALGORITHM

   g-MBMAP- denoted by Bk(f,m,i) the benefit for flow f from assigning message m to device i at the kth iteration of the algorithm. Initially, for every message m, device i and flow f, set B1(f; m; i) B(f; m; i). Then, for k= 1 to j do:

   1. Run algorithm ALG for the Knapsack problem on the following instance. The knap-sack size is size(ik). The items to be packed are the set of messages M. The benefit for every m

      £M is f £ F Bk(f; m; ik), and the weight for every m £ M is size(m).Let Nk be the set of messages selected by ALG.

      j=1

   2. If k = |I|, return T=U|I| {Nj*{ij}}.

      k

      k

   3. For every message m ,device I, and flow f £ F : Decompose the benefit function Bk(f; m; i) into two functions B 1(f; m; i) and B 2(f; m; i) such that

      k

      the following holds: a)B 1 (f, m, i)

      Bk (f, m, i) for i = ik

      min Bk(f, m, i).Bk(f, m, ik) for i ik

      = And m Nk

      0 otherwise

      k

      k

      b) B 2(f, m, i)=Bk(f, m, i) – B 1(f, m, i).

      k

      • Set Bk+1(f, m, i)=B 2(f, m, i)

   g-E-MBMAP-denoted by Bk1(f; m; i) the benefit for flow f from assigning message m to device i at the kth iteration of the algorithm.Initially, for every message m, device i and flow f, set B1(f; m; i) B2(f; m; i). Then, for k = 1 to j do:

   1. Run algorithm ALG for the Knapsack problem on the following instance. The knap-sack size is size(ik). The items to be packed are the set of messages M. The benefit for every m

      £M is f £ F B 1(f; m; i ), and the weight for every m £ M is

      k k

      on the energy level of nodes. size(m).Let Nk be the set of messages selected by ALG.

   2. If k = |I|, return T=U|I| {N *{i }}.

      k k

      j=1 j j

      L-E-MBMAP using an algorithm for a generalization of the Budgeted Maximum Coverage Problem (BMCP).BMCP is defined as follows. Let S be a collection of sets with associated costs defined over a domain of weighted elements. Let L be a budget. Find a subset S S such that the total cost of sets in S does not exceed, and the total weight of elements covered by S is maximized. Generalized Budgeted Maximum Coverage Problem (GBMCP) as follows. Let S be a collection

   3. For every message m ,device I, and flow f £ F Decompose the benefit function B 1(f; m; i) into two functions B 1(f; m; i) and B 2(f; m; i).such that the following holds:

   k

   a)

   B(f, m, i)= B(f, m, i), for i = i

   Min B (f, m, i),B (f) for i i

   of sets with associated costs, k k k

   where every set includes weighted elements. Find a subset of S` S such that the total cost of sets in does not exceed the

   budget L, and the total weight of elements covered by S` is maximized. In the generalized problem, an element may have different weights in different sets. The algorithm for BMCP described in can be easily extended for GBMCP while guaranteeing the same approximation ratio 1-(1/e) variation for BMCP, referred to as The Generalized Maximum Coverage Problem, and present an ((e/(e-

   Where the minimum of two benefit vector is a vector,such that the value of every element is the minimum between its values in the two vectors

   k

   1. Bk(f, m ,i)=Bk(f, m, i)-B 1(f, m, i).

      k

      • Set Bk+1 (f, m, i) B 2(f, m, i)

   L-MBMAP its most important property is that no communication infrastructure is needed between the IDDs. Local MBMAP transferred the message within the o ne cluster. small area coverage to pass information.

   Solve the l-E-MBMAP using an algorithm for a generalization of the Budgeted Maximum Coverage Problem (BMCP). BMCP is defined as follows. Let S be a collection of sets with associated costs defined over a domain of weighted elements. Let L be a budget. Find a subset S S such that the total cost of sets in does not exceed, and the total weight of elements covered by S is maximized.

   Generalized Budgeted Maximum Coverage Problem (GBMCP) as follows. Let S be a collection of sets with associated costs, where every set includes weighted elements. Find a subset of S` S such that the total cost of sets in does not exceed the budget L , and the total weight of elements covered by S` is maximized. In the generalized problem, an element may have different weights in different sets. The algorithm for BMCP described in can be easily extended for GBMCP while guaranteeing the same approximation ratio variation 1-(1/e) for BMCP, referred to as The Generalized Maximum Coverage Problem, and present an ((e/(e-1)+e) approximation for every e>0. In this variation, not only does the benefit of the element differ from one subset to another, but also its weight.

6. PERFORMENCE ANALYSIS

Compare and analysis the normalized benefit and packet drops of the four algorithms, its represented as graphs as follows.

Compare each of the four algorithm with packet transfer and time. Fig 5.1 shows the results of normalized benefit of four algorithm while the y axis indicates the number of packets , x axis indicates the time to be taken for transfer the packets, x indicates the under packet drops to be taken the time.

fig 5.2 shows the results of packet drops of four algorithm. while th y axis indicates the number of packets

Fig 5.1 normalized benefit of four algorithms

Fig 5.2 packet drops of four algorithms

To conclude this section finally G-E-MBMAP gives the highest normalized benefit and less packet drops, compare with other algorithm.

CONCLUSIONS

Develop the models and algorithms for efficient location- based decision-supporting content distribution to mobile groups. It indicated that the cooperative solutions, in which the assignment is made for all the IDDs together, are significantly better than the non cooperative ones. It consists of node localizability testing, structure analysis, and network adjustment and its avoid the network deployment.

Compare and performance to be evaluated the packet drop and normalized benefit of the four algorithm. They are G- MBMAP, L-MBMAP, G-E-MBMAP, L-E-MBMAP.finally

G-E-MBMAP gives the highest normalized benefit and less packet drops, compare with other algorithm.

REFERENCES

1. Mhameed Aezladen,Reuven Cohen,efficient location based decision supporting content distribution to mobile groups ieee/acm transactions on networking, vol. 20, no. 5, october 2012.

2. Acharya.S, Alonso.R, Franklin .M, and Zdonik.S, Broadcast disks: Data management for asymmetric communication environments, proc.ACM SIGMOD, pp 199-210,1995.

3. X. Hong,M.Gerla,G. Pei, and C. Chiang, A group mobility model for ad hoc wireless networks, in Proc. 2nd ACM Int. Workshop Model., Anal. Simulation Wireless Mobile Syst., 1999, pp. 5360.

4. S. Khuller, A. Moss, and J. S. Naor, The budgeted maximum coverage problem, Inf. Process. Lett., vol. 70, no. 1, pp. 3945, 1999.

5. Samal.S, Mobility pattern aware routing in mobile ad hoc network Virginia Polytechnic Institute and State University, Blacksburg,2003.

6. Zhou.B, Xu.K, and Gerla.M, Group and swarm mobility models for ad hoc network scenarios using virtual tracks, in proc.IEEE MILCOM.2004,vol .1.pp.289-294,2003.

7. Cohen.R and Katzir.L, The generalized maximum coverage problem, Inf.n Process. Lett., vol. 108, no. 1, pp. 1522,2008.

8. Cohen, Katzir, and Raz.D, An efficient approximation for the generalized assignment problem,Inf.n process let.,vol.108.no.1.pp.15- 20,2008.