The research paper published by IJSER journal is about Engineering wireless mesh networks: Joint scheduling, Routing, power control and rate adaptation networks with bottleneck algorithm 1

ISSN 2229-5518

Engineering Wireless Mesh Networks: Joint Scheduling, Routing, Power control and Rate Adaptation Networks with Bottleneck Algorithm

Mohammad Khalaf Rahim Al-juaifari, Dr. B.Padmaja Rani

Abstract— the main objective function for our paper is to maximize the minimum throughput among all flows in wireless mesh networks. For this, we first develop new system that add three different module s: first is bottleneck algorithm to avoid dropping the packet during routing, and distributed algorithm to enhance the scheduling of packet via channels with different bandwidth and choose the optimal path according to the highest bandwidth, along with that we add maintenance procedure to manage the power control and rate adaptat ion in wireless mesh networks.

We also quantify the advantage of multihop over single hop, showing that multi- path optimal routing is not much more efficient than single- path optimal routing and that not all min hop routing are equally efficient.

Index Terms— W ireless Mesh Networks, routing, scheduling, power control, rate adaptation, Bottleneck algorithm,Simplex algorithm.

——————————  ——————————

1 Introduction

he Researchers working in the area of wireless communi- cations heavily rely on simulations to evaluate the per- formance of proposed algorithms. This is primarily be- cause setting up large scale wireless tested and ensuring re-
peatability across multiple tested is a difficult task.
Mesh networks are different – full physical layer connectiv-
ity is not required. As long as a node is connected to at least
one other node in a mesh network, it will have full connectivi- ty to the entire network because each mesh node forwards packets to other nodes in the network as required. Mesh pro- tocols automatically determine the best route through the
network and can dynamically reconfigure the network if a link becomes unusable.

2 Related Works

Jain et al. [1] were among the first to formulate a joint routing and scheduling problem for wireless networks valid for all linear objective functions, including maximum- minimum. The framework they proposed is rather compre- hensive: it includes both the protocol and the physical interfe-

————————————————

Mohammad Khalaf Rahim Al-juaifari is currently pursuing masters degree program in computer science and engineering department in Jawaharlal Nehru Technological University Hyderabad, Indai, PH-00914023158661. E-mail: hyd2_jntuadm@sancharnet.in
Dr.B.Padmaja Rani is PHD in computer science and engineering de- partment in Jawaharlal Nehru Technological University Hydera- bad, Indai, E-mail: hyd2_jntuadm@sancharnet.in
rence models, an extension of which is used in this project,
and it can accommodate physical technologies such as mul- tiple radios and non-overlapping channels. One limitation is that power control and rate adaptation are not considered. Jain et al. only provide upper bounds obtained by applying clique feasibility conditions and lower bounds obtained by using subsets of all schedulable link sets.
Zhang et al. [2] apply column generation to solve a similar problem in multi-radio and multi-channel networks.
In [3] using additive interference model does not consi- dering power control and rate adaptation within the work
By using [2] ,additive interference model with multi power and multi-rate for solving problem [1].
A similar characterization is distinct contribution applied in [5], [2] to construct a new routing metric called interference clique transmission time, though it is not clear how practic-
al such a scheme can be.
There also exists another body of work applying online dy-
namic control for throughput maximization [6].
in [7] to construct a new routing metric called interference clique transmission time, though it is not clear how practical such a scheme can be.
any attempt at approximating the NP-complete sub prob- lems may drastically reduce the performance [8].
Column generation method has been applied intensively to the cross-layer design of multihop wireless networks.
In[4] making use of a greedy heuristic to obtain suboptimal solutions it does not scale with an increasing problem size and yields to optimal solutions [9].
Jun Luo [10] accommodates physical technologies such as multiple radios and non-overlapping channels.
A new extension in our paper related to use two algorithms with procedure to enhance WMNS Its working mainly de-
pending on bottleneck algorithm.

http://www.ijser.org

The research paper published by IJSER journal is about Engineering wireless mesh networks: Joint scheduling, Routing, power control and rate adaptation networks with bottleneck algorithm 2

ISSN 2229-5518

Moreover for formulating a joint routing and scheduling problem for wireless networks valid for all linear objective
functions, the framework includes both the protocol and the physical interference models.
There have been many attempts to extend this optimization framework and to improve the algorithms that solve it.
The computation of SINR (Signal to Interference and Noise Ratio) should take into account the sum of the strengths of all the interfering signals instead of just the strongest interfering signal [11].
The channel gain model should be comprehensive in that it should include distance based path loss, location dependent shadowing, and velocity dependent fading [11].

3 Network Model and Problem Formulation

1- IP Formulation: Will be transformed to ILP Objec- tive Function.

2- Objective Function: Minimize the number of used

slots

4 System Proposed Architecture

In general Column Generation Model, column generation means that not all variables will be considered explicitly; columns will be added to the problem ―on the fly‖
Pricing problem is ILP(takes long time) In column generation model, instead of solving pricing problem, use greedy algorithm to see if solution can be improved.
The Internet is comprised of packet-processing nodes, called routers, that route packets towards their destinations, and physical links that transport packets from one router to another. Every router is required to perform a forwarding decision on an incoming packet to deter- mine the packet’s next-hop router.
A formal description of our distributed scheduling framework is as
follows. It is composed of four phases:
1. Utility exchange. Each node exchanges the utility function of each
of its incoming and outgoing links with its neighbors.
2. Initial decision. Each node chooses the link with best utility to be
the initial decision of next communication.
3. Initial decision exchange. Nodes with an initial decision of
―transmit‖ – the best link of that node is an outgoing link – broadcast
the initial ―transmit‖ decision to all its one-hop neighbor nodes via a control channel.
The control message indicates the IDs of the intended transmitting (origin) and receiving (destination) nodes associated with the initial decision.
4. Final decision., y Each node with an initial decision of ―transmit‖

checks if the desired receiving node is having the same ―transmit‖ initial decision based on the control messages in Phase 3. If so, the node gives up the intended transmission. If not, the node starts transmission in that direction in next slot.
y Each node with an initial decision of ―receive‖ find out the best
transmitter based on the control
Messages in Phase 3, and configures its physical
layer to be ready to receive data from that direction in the next time
slot.
Distributed algorithm the channel assignment problem in the pro-
posed multi-channel wireless mesh network architecture can be di- vided into two sub problems - (1) neighbor to-interface binding, and (2) interface-to-channel binding. Neighbor-to-interface binding de- termines through which interface a node communicates with each of its neighbors. Because the number of interfaces per node is limited, each node typically uses one interface to communicate with multiple of its neighbors. Interface-to-channel binding determines which radio channel a network interface uses. The main constraints that a channel assignment algorithm needs to satisfy are:
1. The number of distinct channels that can be assigned to a wireless
mesh network node is limited by the number of NICs on it,
2. Two nodes involved in a virtual link that is expected to carry some
trafﬁc should be bound to a common channel,
3. The sum of the expected loads on the links that interfere with one another and that are assigned to the same channel cannot exceed the channel’s raw capacity, and
4. The total number of radio channels is ﬁxed.
At a ﬁrst glance, this problem appears to be a graph-coloring prob- lem. However, standard graph coloring algorithms cannot really cap- ture the specification and constraints of the channel assignment prob- lem. A node-multi-coloring formulation fails to capture the second constraint where communicating nodes need a common color. On the other hand, an edge-coloring formulation fails to capture the ﬁrst constraint where no more than (number of NICs per node) colors can

http://www.ijser.org

The research paper published by IJSER journal is about Engineering wireless mesh networks: Joint scheduling, Routing, power control and rate adaptation networks with bottleneck algorithm 3

ISSN 2229-5518

be incident to a node. While a a constrained edge-coloring might be able to roughly model the remaining constraints, it is incapable of satisfying the third constraint of limited channel capacity

Figure 1: Basic ﬂow chart discussing various aspects of trafﬁc engi- neering in multi-channel mesh network architecture.
The using of K-Connection traffic Maintenance Procedure:
For maintain N connections the following procedure must be follow by VB node in the network.
Algorithm 3 k=N connection maintenance.
1: VB periodically send the number of connection information to all the one hop nodes.
2: one hop nodes send their attachment to other VB details to origi- nating VB.
3: if k=7 (3 rd case), VB reserved one R-VB for Upcoming connec- tion request then
4: if k=N then (all VB nodes are connected)
5: share the connection between one hop R-VB (k=3or 5)
6: else (k>5, balance routing is not sufficient)
7: connect the node to best neighbor
8: end if
9: end if
The updating of connection balancing is done locally between the VB and other nodes. In this way all local computation supports con- nection balancing routing in the network.

Figure 2: Connections Balancing in Virtual-Backbone (VB)
In both figures drawn below describing of whole proposed system
Figure 2: Node side for system proposed

Figure 3: Server side for system proposed server side
In figure 2,3 above describe the way of system working in both node and server side, the main idea is that adding bottle neck algorithm to avoid packet dropping during routing, and managing the packet to high bandwidth channel by using distributed algorithm.

5 Numerical Results

We have chosen to present the results in terms of the aver- age flow rate as opposed to the value of the objective func- tion since the fairness measure does not mean too much practically.

We have to mention that results below did not cover all possible so- lution rather than take care about specific case in two different ways.

http://www.ijser.org

The research paper published by IJSER journal is about Engineering wireless mesh networks: Joint scheduling, Routing, power control and rate adaptation networks with bottleneck algorithm 4

ISSN 2229-5518

Figure 4: results with using same channel with different size of packet (single hop)

Figure 5: results with using different channel with different size of packet (multiple hops)

Figure 6 Results with Using Different Channel with Differ- ent Size of Packet (multiple-hops).

6 Conclusion

WMNs can be built up based on existing technologies, field trials and experiments with existing WMNs prove that the performance of WMNs is still far below expectations.
As explained throughout this article, there still remain many research problems.
This paper proposes a study of the optimal configurations of fixed mesh networks using conflict free scheduling.
These results are obtained by developing two computational tools to solve exactly the joint routing, scheduling, power control and rate adaptation problem.
The proposed system used first bottleneck algorithm to transfer packet from one client to another, it is used to avoid packet losing during routing operation.
Second distributed algorithm using for joint scheduling packet, the
new scheduling algorithm is fully distributed, capable of selecting high utility link combinations to achieve opportunistic gain, and ge- nerating reasonably temporal-correlated interference to ensure distri- buted power control and scheduling performance.
We have to know that is very hard to do routing, scheduling, power and rate control in a real network, because it needs to be node syn- chronized band done quickly in the presence of changing channel conditions.

Refrences

[1] K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu, ―Impact of Interferenceon Multi-hop Wireless Network Performance,‖ in Proc. of the 9th ACMMobiCom, 2003.

[2] J. Zhang, H. Wu, Q. Zhang, and B. Li, ―Joint Routing and

Scheduling

in Multi-radio Multi-channel Multi-hop Wireless Networks,‖ in

Proc. of

the 24th IEEE INFOCOM, 2005.

[3] A. Iyer, C. Rosenberg, and A. Karnik, ―What is the Right

Model for

Wireless Channel Interference,‖ IEEE Transaction Wireless

Communications,

[4] M. Johansson and L. Xiao, ―Cross-Layer Optimization of

Wireless Networks

Using Nonlinear Column Generation,‖ IEEE Trans. on Wireless

Communications, vol. 5, no. 2, pp. 435–445, 2006.

[5] H. Zhai and Y. Fang, ―Impact of Routing Metrics on Path

Capacity in

Multirate and Multihop Wireless Ad Hoc Networks,‖ in Proc. of the

14th IEEE ICNP, 2006.

[6] A. Eryilmaz and R. Srikant, ―Fair resource allocation in

wireless

networks using queue-length based scheduling and congestion

control,‖

in Proc. of the 24th IEEE INFOCOM, 2005.

[7] L. Georgiadis, M. Neely, and L. Tassiulas, ―Resource

Allocation andCross-Layer Control in Wireless Networks,‖ Foundations and

Trends in

Networking, vol. 1, no. 1, pp. 1–144, 2006.

[8] X. Lin and N. Shroff, ―The impact of imperfect scheduling on cross-layer

rate control in wireless networks,‖ in Proc. of the 24th IEEE

INFOCOM,

2005.

[9] A. Capone and G. Carello, ―Scheduling Optimization in

Wireless MESH

Networks with Power Control and Rate Adaptation,‖ in Proc. of

the 3rd

IEEE SECON, 2006.

http://www.ijser.org

International Journal of Scientific & Engineering Research Vo lume 3, Issue 9, September-2012 5

ISSN 2229-5518

[10] Jun Luo_, Catherine Rosenbergt and Andr'e Girard "Engineering Wireless Mesh Networks: JointScheduling, Routing, Power Control andRateAdaptation" 2010

[11]A Novel Distributed Scheduling Algorithm for Wireless Mesh

Networks* Yun Hou and KinK. Leung

Imperial College London SW7 2BT, United Kingdom {yun.hou, kin .Ieung}@imperial.ac.uk

IJSER lb)2012 h tt p ://www .'lser. org