My work is proposed for general resource sharing prob- lems, which gives solution for congestion control and throughput utility maximization
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1362
ISSN 2229-5518
Improvisation of CSMA in multi-hop wireless network using Markov chain model
Vivekanand
Abstract— The first contribution in this paper is to introduce a distributed adaptive carrier sense multiple access (DCSMA) algorithm for a general interference model. It is inspired by CSMA, but maybe applied to more general resource sharing problems (i.e., not limited to wireless networks). We show that if packet collisions are ignored (as in some of the mentioned references), the algorithm can achieve maximal throughput by using Markov chain model which is used for scheduling the path for data transmission. The contribution is to combine the proposed scheduling algorithm with congestion control using a novel technique to achieve fairness among competing flows as well as maximal throughput.
—————————— ——————————
My work is proposed for general resource sharing prob- lems, which gives solution for congestion control and throughput utility maximization
Congestion control concerns controlling traffic entry into a telecommunications network, so as to avoid congestive collapse by attempting to avoid oversubscription of any of the processing or link capabilities of the intermediate nodes and networks and taking resource reducing steps, such as reducing the rate of sending packets. It should not be con- fused with flow control, which prevents the sender from overwhelming the receiver.
It is a procedure for scheduling data packets in a packet- switched best-effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wire- less network
The system- architecture has been shown below for max- imizing throughput and utility maximization using Mar- kov chain model in a multi-hop wireless network by using an improvised distributed adaptive carrier sense multiple access algorithm (DCSMA).
Markov chain model is used for scheduling the path for data transmission. Transitions of the transmission states are observed perfectly to form a continuous-time Markov chain, which is called the CSMA Markov chain. If there are two links with an edge between them, which means that they cannot transmit together. State (0,0) means that no link is transmitting, state (1,0) means that only link 1 is trans- mitting, and (0,1) means that only link 2 is transmitting. The state (1,1) is not feasible. Markov Property: means that the state of the system at time t+1 only depends on the state of the system at t. A Markov chain is a random process with the Markov property, i.e. the property that the next state depends only on the current state and not on the past.Congestion control with the CSMA scheduling algo- rithm to achieve fairness among competing flows as well as the maximal throughput. Here, the input rates are distrib- utedly adjusted by the source of each flow.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1363
ISSN 2229-5518
Link Weight Manipulation
From neighbours, link weight for each and every link in
A wireless ad hoc network is a decentralized wireless the network can be identified, which also represents the link
network. The network is ad hoc because it does not rely on weight between each and every nodes.
a pre existing infrastructure, such as routers in wired net-
works or access points in managed (infrastructure) wireless networks. Instead, each node participates in routing by forwarding data for other nodes, and so the determination of which nodes forward data is made dynamically based on the network connectivity. Each and every node in the network detects its neighbour node, which will be used for establish link and identifying of routing path in future.
A wireless ad hoc network consists of a collection of mobile nodes interconnected by multi-hop wireless paths with wireless transmitters and receivers. Such net- works can be spontaneously created and operated in a self- organized manner, because they do not rely upon any pre- existing network infrastructure. In particular, it is not easy to achieve the maximal throughput through distributed scheduling, which in turn prevents full utilization of the wireless network. Scheduling is challenging since the con- flicting relationships between different links can be compli- cated.
Neighbour Nodes detection
IJSER
Each and every nodes in the network, detects for its neigh-
bour nodes.
Each node shares there link weight between the neighbour nodes. While CSMA routing defers the final route selection, the candidate forwarding nodes should still be selected in advance.
The shortest path problem is the problem of find- ing a path between two nodes such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to an- other on a road map; in this case, the vertices represent lo- cations and the edges represent segments of road and are weighted by the time needed to travel that segment and we manipulate through link weight.
For joint scheduling and congestion control, however, directly
using the expression of service rate will lead to a non-convex problem
Path Manipulation
After identifying the link weight, destination can be cho- sen. For the given source and destination, path manipula- tion is done using CSMA Markov chain model.
The links in the networks where each link is a transmit- ter and receiver. Two links cannot transmit at the same time (i.e., “conflict”) if there is an edge between them. The message transfer framework also includes the
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1364
ISSN 2229-5518
“node-exclusive model” and “two-hop interference model”.
If the transmitter of link senses the transmission of any conflicting link, then it keeps silent. If none of its conflicting links is transmitting, then the transmitter of link waits (or backs off) for a random period of time and then starts its transmission.
Markov chain model is used for scheduling the path for data transmission. Transitions of the transmission states are observed perfectly to form a continuous-time Markov chain which is called the CSMA Markov chain. If there are two links with an edge between them, which means that they cannot transmit together. State (0, 0) means that no link is transmitting, state (1, 0) means that only link 1 is transmitting, and (0,1) means that only link 2 is transmit- ting. The state (1,1) is not feasible Markov Property: means that the state of the system at time t+1 only depends on the state of the system at t. A Markov chain is a random pro- cess with the Markov property, i.e. the property that the next state depends only on the current state and not on the past. Congestion control with the CSMA scheduling algo-
rithm to achieve fairness among competing flows as well as
In multi-hop wireless networks, it is important to efficient- ly utilize the network resources and provide fairness to competing data flows. These objectives require the cooper- ation of different network layers. The transport layer needs to inject the right amount of traffic into the network based on the congestion level, and the MAC layer needs to serve the traffic efficiently to achieve high throughput. Through a utility optimization framework, this problem can be natu- rally decomposed into congestion control at the transport layer and scheduling at the MAC layer.
It turns out that MAC-layer scheduling is the bottleneck of the problem. In particular, it is not easy to achieve the max- imal throughput through distributed scheduling, which in turn prevents full utilization of the wireless network. Scheduling is challenging since the conflicting relationships between different links can be complicated.
It is well known that maximal-weight scheduling (MWS) is throughput-optimal. That is, that scheduling can support any incoming rates within the capacity region. In MWS, time is assumed to be slotted. In each slot, a set of non con-
flicting links (called an “independent set,” or “IS”) that
IJSER
the maximal throughput. Here, the input rates are distrib-
utedly adjusted by the source of each flow.
The message transfer occurs by doing the scheduling process in edge using markov chain model. Thus the con- gestion in the network can be avoided, whereas through- put can be maximized.
have the maximal weight are scheduled, where the
“weight” of a set of links is the summation of their queue
lengths. (This algorithm has also been applied to achieve
100% throughput in input-queued switches.) However,
finding such a maximal-weighted IS is NP-complete in
general and is hard even for centralized algorithms. There-
fore, its distributed implementation is not trivial in wireless
networks.
A few recent works proposed throughput-optimal algo-
rithms for certain interference models. For example, Eryil-
maz et al. proposed a polynomial-complexity algorithm for
the “two-hop interference model”.1 Modiano et al. intro-
duced a gossip algorithm for the “node-exclusive model”.2
The extensions to more general interference models, as dis-
cussed , involve extra challenges. Sanghavi et al. intro-
duced an algorithm that can approach the throughput ca-
pacity (with increasing overhead) for the node-exclusive
model. On the other hand, a number of low-complexity but
suboptimal scheduling algorithms have been proposed in
the literature.
By using a distributed greedy protocol similar to IEEE
802.11, shows that only a fraction of the throughput region
can be achieved (after ignoring collisions). The fraction de-
pends on the network topology and interference relation-
ships. The algorithm is related to Maximal Scheduling,
which chooses a maximal schedule among the nonempty
queues in each slot. Different from Maximal Scheduling,
the Longest-Queue-First (LQF) algorithm takes into ac-
count the queue lengths of the nonempty queues. It shows
good throughput performance in simulations. In fact, LQF
is proven to be throughput-optimal if the network topology
satisfies a “local pooling” condition or if the network is
small. In general topologies, however, LQF is not through-
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1365
ISSN 2229-5518
put-optimal, and the achievable fraction of the capacity region can be characterized .It has been studied the impact of such imperfect scheduling on utility maximization in wireless networks, Proutiere et al. developed asynchronous random-access-based scheduling algorithms that can achieve throughput performance similar to that of the Max- imum Size scheduling algorithm. Our first contribution in this paper is to introduce a distributed adaptive carrier sense multiple access (CSMA) algorithm for a general inter- ference model. It is inspired by CSMA, but may be applied to more general resource sharing problems (i.e., not limited to wireless networks). We show that if packet collisions are ignored (as in some of the mentioned references), the algo- rithm can achieve maximal throughput. The optimality in the presence of collisions is studied. The algorithm may not be directly comparable to those throughput-optimal algo- rithms we have mentioned since it utilizes the carrier- sensing capability. However, it does have a few distinct features:
• Each node only uses its local information (e.g., its back- log). No explicit control messages are required among the nodes.
• It is based on CSMA random access, which is similar to
the IEEE 802.11 protocol and is easy to implement.
• Time is not divided into synchronous slots. Thus, no syn-
time is slotted and Link, which as high weight is processed but finding Maximal weight is hard in the wireless network.
On the other hand, a number of low-complexity but suboptimal scheduling algorithms have been proposed in the literature. By using a distributed greedy protocol similar to IEEE 802.11, shows that only a fraction of the throughput region can be achieved (after ignoring collisions). The fraction depends on the network topology and interference relationships. The algorithm is related to Maximal Scheduling, which chooses a maximal schedule among the nonempty queues in each slot. Different from Maximal Scheduling, the Longest-Queue- First (LQF) algorithm takes into account the queue lengths of the nonempty queues. It shows good throughput performance in simulations. In fact, LQF is proven to be throughput-optimal if the network topology satisfies a “local pooling” condi- tion or if the network is small. In general topolo- gies, however, LQF is not throughput-optimal, and the achievable fraction of the capacity region can be
characterized.
chronization of transmissions is needed.
In a related work, Marbach et al. studied a model of
CSMA with collisions. It was shown that under the “node-
exclusive” interference model, CSMA can be made asymp-
totically throughput-optimal in the limiting regime of large
networks with a small sensing delay. Rajagopalan and
Shah independently proposed a randomized algorithm
similar to ours in the context of optical networks. However,
there are some notable differences (e.g., the use of Theorem
1 here). Also, utility maximization (discussed below) was
not considered.
In older days people have been using two types of algorithm-
MAC-layer scheduling is the bottleneck of the problem. In particular, it is not easy to achieve the maximal throughput through distributed schedul- ing, which in turn prevents full utilization of the wireless network. Scheduling is challenging since the conflicting relationships between different links can be complicated.
Disadvantages:-
In transport layer amount of flow control
Is and MAC layer is responsible for maximal
Throughput but this is not achieved through
Distributed scheduling.
In Maximal weight scheduling a
Our first contribution in this paper is to introduce a distributed adaptive carrier sense multiple access (CSMA) algorithm for a general interference mod- el. It is inspired by CSMA, but maybe applied to more general resource sharing problems (i.e., not limited to wireless networks). We show that if packet collisions are ignored (as in some of the mentioned references), the algorithm can achieve maximal throughput. The algorithm may not be di- rectly comparable to those throughput-optimal al- gorithms we have mentioned since it utilizes the carrier-sensing capability.
The advantage of the proposed system is that there is no limitation to wireless networks. Here, the packet collisions are ignored. The other advantage in the proposed system is that the maximum throughput is achieved through CSMA Markov chain model.
In 1999, Sun acquired Net Beans Developer from Net Beans and rebranded it as Forte for Java Community Edition (Sun acquired Forte in 1999). In 2000, Sun made the Net Beans IDE open source.
GUI that lets the user better knows the existence of that
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1366
ISSN 2229-5518
particular functionality and its easier for them to click and select than type something on a black boring screen. Thus, today’s developers need IDE’s such as net beans that develop ready made windows forms with
all the required buttons, labels, text boxes and like that can be tailor made for the program in question.
Carrier Sense Multiple Access (CSMA) is a probabilistic Media Access Control (MAC) protocol in which a node ver- ifies the absence of other traffic before transmitting on a shared transmission medium, such as an electrical bus, or a band of the electromagnetic spectrum.
"Carrier Sense" describes the fact that a transmitter uses feedback from a receiver that detects a carrier wave before trying to send. That is, it tries to detect the presence of an encoded signal from another station before attempting to transmit. If a carrier is sensed, the station waits for the trans-
Message to be transferred from source to destination.
mission in progress to finish before initiating its own trans- mission.
"Multiple Access" describes the fact that multiple stations send and receive on the medium. Transmissions by one node are generally received by all other stations using the medium.
7.1 Snapshots
An acknowledgement at receiver upon receiving message ffrom source.
7.2 ANALYSIS
Source and destination with intermediate nodes with
link weight.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1367
ISSN 2229-5518
Graph showing time taken (ms) by different links at different
Distance.
This work is the first approach towards distributed maxi- mum throughput algorithms for wireless networks. Although we have made a theoretical contribution and have taken implementation constraints into account, much work is required in order to develop truly implement able algo- rithms. Some of the key issues in that context are: (i) how should the control messages is transmitted in a node- exclusive spectrum sharing model, (ii) what are the tradeoffs between throughput, delay, and decentralization costs, and (iii) how can the algorithms deal with an asynchronous network.
Proc. Conf. Inf. Sci. Syst., Princeton, NJ, Mar. 2006, pp.
1254–1259.
[8] X. Wu and R. Srikant, “Scheduling efficiency of
distributed greedy scheduling algorithms in wireless
networks,” in Proc. IEEE INFOCOM, Barcelona,
Spain, Apr. 2006, pp. 1–12.
Current performance analysis of Algorithms is based on a separation of time scales, i.e., the vector is adapted slowly to allow the CSMA Markov chain to closely track the sta- tionary distribution . The results however, indicate that such slow adaptations are not always necessary. In the fu- ture enhancements, more about the case without time-scale separation can be performed.
[1] X. Lin, N. B. Shroff, and R. Srikant, “A tutorial on cross-layer optimization in wireless networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1452–1463, Aug. 2006.
[2] L. Jiang and J. Walrand, “A distributed CSMA al- gorithm for throughput and utility maximization in wireless networks,” in Proc. 46th Annu. Allerton Conf. Commun., Control, Comput., Sep. 23–26, 2008, pp. 1511–1519.
[3] A. Eryilmaz, A. Ozdaglar, and E. Modiano, “Poly-
nomial complexity algorithms for full utilization of multi-hop wireless networks,” in Proc. IEEE INFO- COM, Anchorage, AK, May 2007, pp. 499–507.
[4] E. Modiano, D. Shah, and G. Zussman, “Maximiz- ing throughput in wireless networks via gossiping,”
ACM SIGMETRICS Perform. Eval. Rev., vol. 34, no. 1, pp. 27–38, Jun. 2006.
[5] S. Sanghavi, L. Bui, and R. Srikant, “Distributed link scheduling with constant overhead,” in Proc. ACM SIGMETRICS, Jun. 2007, pp. 313–324.
[6] J. W. Lee, M. Chiang, and R. A. Calderbank, “Utili- ty-optimal random-access control,” IEEE Trans. Wire- less Commun., vol. 6, no. 7, pp. 2741–2751, Jul. 2007. [7] P. Gupta and A. L. Stolyar, “Optimal throughput allocation in general random access networks,” in
IJSER © 2013 http://www.ijser.org