第1页 / 共260页
第2页 / 共260页
第3页 / 共260页
第4页 / 共260页
第5页 / 共260页
第6页 / 共260页
第7页 / 共260页
第8页 / 共260页
ns2中AOMDV_Scheduling源代码以及评测.pdf
Institut für
Technische Informatik und
Kommunikationsnetze
Evaluation of Scheduling Methods over
Multipath Routing in Wireless Mobile
Ad Hoc Networks
Semester Thesis, SA-2006-26
SS 06, April 2006 - July 2006
Authors:
Regula Gönner
Dominik Schatzmann
Professor: Bernhard Plattner
Georgios Parissidis
Advisor:
Institut für
Technische Informatik und
Kommunikationsnetze
Summer Semester 2006
Semester Thesis
for
Regula Gönner (D-ITET), Dominik Schatzmann (D-ITET)
Main Reader:
Alternate Reader: Martin May
Georgios Parissidis
Issue Date:
Submission Date:
3. April 2006
30. June 2006
Evaluation of scheduling methods over multipath routing
in wireless mobile Ad Hoc networks
1 Introduction
Multi-path routing is not a new concept and has been proposed and implemented in packet and circuit
switched networks.
In circuit switched telephone networks alternate path routing was proposed in
order to increase network utilization as well as to reduce the call blocking probability. However, the
wide deployment of multi-path routing is so far prevented due to higher complexity and the additional
cost of extra routes that need to be stored in the routers.
Analysis and comparison of single path and multi-path routing with load balance mechanisms in ad
hoc networks in terms of protocol overhead, traffic distribution and throughput has been conducted
in [1]. The results reveal that in comparison with single-path routing, multi-path routing achieves higher
throughput and increases network capacity. As the dimensions of mobile ad hoc networks are spatially
bounded network congestion is inherently experienced in the center of the network as shortest paths
mostly include nodes that are located at the center of the network. Thus a protocol in order to route data
packets over non-congested links and maximize overall network throughput should target at utilizing
the maximum available capacity of the calculated multiple routes. The authors concluded that routing
or transport protocols in ad hoc networks should provide appropriate mechanisms to push the traffic
further from the center of the network to less congested links.
In [2] the effect of the number of multiple paths on routing performance has been studied using an
analytical model. Their results showed that multi-path routing performs better than single path if the
1
number of alternative paths is limited to few paths. Simulation results of their model demonstrated
that with multi-path routing end-to-end delay is higher as alternate paths tend to be longer.
The goal of the present thesis is to conduct a performance evaluation of scheduling algorithms over
multipath routing for mobile wireless Ad Hoc networks. Therefore, the main objectives of the present
thesis are:
1. Implement and conduct a performance evaluation of scheduling algorithms (Round Robin, Weighted
Round Robin, Proportional selection of paths) over a multipath routing protocol in mobile wireless
Ad Hoc networks.
2. Propose and implement an optimized scheduling algorithm tailored for mobile wireless Ad Hoc
networks that maximizes the throughput as well as minimizes the average end-to-end delay.
2 Conceptual Formulation
Wireless ad hoc networks consist of many features that differentiate them from conventional wired
networks. The non-employment of multi-path routing in the standardized routing protocols used in
the Internet today does not imply that multi-path routing is not an appropriate and promising solution
for wireless mobile ad hoc networks. The unreliability of the wireless medium, the unpredictability of
the network topology as node failures may occur frequently and the dynamic topology due to mobility
of nodes result to frequent path breaks, network partitioning and high delays of path re-establishments.
Multi-path routing represents a promising routing method for wireless mobile ad hoc networks. Multi-
path protocols establish multiple disjoint paths to the same destination. Thus, the probability of dis-
connection from the sender to the receiver is effectively reduced. Multi-path routing achieves load
balancing of data traffic across network elements which is especially important in resource constrained
environments, like mobile wireless ad hoc networks, where power is scarce and limited. Furthermore,
multi-path routing attains more efficient protection to attacks. Spreading traffic over multiple paths, at-
tacks such as packet interception and traffic analysis are much harder to perform. A multi-path routing
protocol should fulfill the following properties:
• The routing protocol must provide multiple, loop-free and preferably node-disjoint paths to des-
tinations. These two properties represent a strong measure of path independence.
• The multiple paths should be used simultaneously for data transport.
• Multiple routes need to be known at the source.
A multi-path routing protocol for mobile ad hoc networks that satisfy the above-mentioned properties
is the AOMDV [3]. AOMDV extends the AODV [4] to provide multiple paths. In AOMDV each RREQ and re-
spectively RREP defines an alternative path to the source or destination. Multiple paths are maintained
in routing entries in each node. The routing entries contain a list of next-hops along with corresponding
hop counts for each destination To ensure loop-free paths AOMDV introduces the advertised_hop_count
value at node i for destination d. This value represents the maximum hop-count for destination d avail-
able at node i. Consequently, alternate paths at node i for destination d are accepted only with lower
hop-count than the advertised_hop_count value.
An implementation of the AOMDV protocol in ns is available, however in the original implementation
only one path is used at a time. Alternative paths are used as backup paths. Therefore, a modification
of the original AOMDV source code should be done to implement the studied scheduling methods.
Primarily, for the first part of the thesis we consider the following scheduling algorithms:
2
1. Round Robin: In this scheduling algorithm, a path is selected with the same probability among
the multiple paths at the time a data packet is sent. Therefore, assuming that at time t, n paths
are known at a sender s towards the destination d. A path i is selected with probability pi :
pi =
1
n
,
n
X
i=1
pi = 1, i ∈ [1, n].
(1)
2. Weighted Round Robin: The weighted Round Robin algorithm represents an special case of the
Round Robin algorithm. On each path i a weight wi is assigned and accordingly a path is selected
with probability pi :
pi = wi,
wi = 1, i ∈ [1, n].
(2)
n
X
i=1
3. Proportional selection of paths: In this algorithm a proportion of available multiple paths is se-
lected at each sender to disseminate data packets towards a destination. We assume two policies
in the way paths are selected:
a) N out of M. Select best N out of total M paths.
b) Use only the best (N=1) out of M paths and keep the rest as backup.
The optimal selection of paths on the "Proportional selection of paths" algorithm, as well as the optimal
assignment of weights for the "Weighted Round Robin" algorithm depend on parameters that inherently
influence the performance of each algorithm:
• Path duration/lifetime. The total time a path is active.
• Path length. The total number of hops between a source and a destination.
• Path breakage probability. The probability that a path will be active at the time a packet is sched-
uled to be sent.
The second part of the thesis complements the performance evaluation of the studied scheduling al-
gorithms. An optimized scheduling algorithm tailored for wireless mobile Ad Hoc that outperforms the
abovementioned algorithms should be proposed and implemented.
3
2.1 Tasks
Summarizing, the essential tasks that need to be addressed in the present thesis are the following:
1. Performance evaluation of the abovementioned algorithms in the ns network simulator [5]. The
performance evaluation should compare the different algorithms using the following metrics:
a) Throughput: The ratio of the total number of packets delivered at the destination to the total
number of data packets sent.
b) Average end to end delay: The average end-to-end delay consists of propagation, queuing,
retransmission at the MAC layer, and buffering delays for successfully delivered data packets.
2. Design and implementation of an optimized scheduling algorithm(s) over multiple paths for wire-
less mobile Ad Hoc networks that achieve higher throughput and lower end-to-end delay.
A detailed timeline and a detailed list including a short description of each task is presented in table 1.
Tasks are distributed evenly in two categories: A and B; one per student.
Tasks
1.
2.
3.
4.
4.1
4.2
4.3
4.4
5.
5.1
5.2
6.
6.1
6.2
6.3
7.
8.
9.
10.
Time
1 week (3 April)
1 week (10 April)
1 week (17 April)
2 weeks (24 April)
24.04 - 01.05
24.04 - 01.05
01.05 - 08.05
01.05 - 08.05
2 weeks (8 May)
08.05 - 22.05
08.05 - 22.05
2 weeks (22 May)
22.05 - 05.06
22.05 - 05.06
22.05 - 05.06
1 week (05 June)
1 week (12 June)
2 weeks (19 June)
30 June
Task Description
Related work
Getting familiar with ns
Installation/of a multipath routing protocol in ns
Implementation of scheduling algorithms
- Round Robin
- Proportional selection of paths
- Weighted Round Robin (incl. parameters)
- Proportional selection of paths (incl. parameters)
Performance evaluation of scheduling algorithms
- RR + WRR
- Prop. selection + Prop. selection (+ par.)
Proposal of optimized scheduling algorithms
- Based on 4.1, 4.2
- Based on 4.2, 4.3
- Intermediate Report
Performance evaluation of proposed scheduling algorithms
Assemble of the results
Thesis report
Submission of final thesis report
A
*
*
*
*
*
*
*
*
*
*
*
*
B
*
*
*
*
*
*
*
*
*
*
*
*
Table 1: Timeline of the thesis
3 Important remarks
1. A final timeplan for the realization of the semester thesis should be made by the end of the first
week and discussed with the supervisor.
2. By the end of the second month a short intermediate report should be composed and reviewed
during a meeting of the students with the supervisors. The intermediate report should list the
already achieved tasks and the tasks that are foreseen to have been accomplished by the end of
the thesis. Strictly speaking the intermediate report should comply with a structural design of the
final report (in a bulleted form).
3. An ordinary contact (at least once a week) between the students and their supervisor has to take
place via telephone, e-mail, meetings, tikiwiki semester thesis web page or other means. During
4
these contacts the progress of the performed work has to be shown and problems should be
discussed. Especially important is the daily reading of e-mails.
4 Thesis Results
A fifteen minutes presentation should be given in TIK Institute. The exact date of the presentation
will be specified late in the summer semester. Apart from this presentation, the following documents
should be handed in:
1. A detailed technical report (Bericht) in English. The following topics should be thoroughly ad-
dressed in this report: a description of the investigated research area, a description of the ex-
amined scheduling algorithms, a listing of the solved and unsolved problems (together with the
reasons why they haven’t been solved), references to literature, table of contents, figures,tables
and potential appendices (glossary, programming code, etc.). The report should end up with an
evaluation of how far the initial tasks of the thesis have been achieved and whether the initial
timeplan was fulfilled. Five copies of the final report should be handed in, all bound and double
sided printed. The technical report is preferred to be composed in Latex.
2. An abstract in both German and English, 1-2 pages long. This should contain a quick overview of
the performed work. The structure of the abstract should be in the form: (1) Introduction, (2) Aims
& Goals, (3) Results, (4) Future Work.
3. An electronic version of the technical report as well as of all the produced documents (code doc-
umentation, models etc.). Figures contained in the final report have to be additionally stored as
independent data in a custom-selected format (ex. EPS). The material in electronic form should
be either stored on a CD or in a separate directory on an institute’s server (accounts should then
be created for the students).
4. Referenced and processed literature, whether in electronic or printed form.
5. The complete source code of the system and of the test codes, together with all the necessary
libraries/external programs.
References
[1] P. Pham and S. Perreau, “Performance analysis of reactive shortest path and multi-path routing
mechanism with load balance,” INFOCOM, San Francisco, CA, USA, 2003.
[2] A. Nasipuri, R. Castaneda, and S. R. Das, “Performance of multipath routing for on-demand protocols
in mobile ad hoc networks,” Mob. Netw. Appl., vol. 6, no. 4, pp. 339–349, 2001.
[3] M. Marina and S. Das, “On-demand multipath distance vector routing in ad hoc networks,” Proceed-
ings of the International Conference for Network Procotols (ICNP), November 2001.
[4] C. E. Perkins, E. M. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (aodv) routing,” RFC
3561, July 2003.
[5] “ns-2: Network simulator,” http://www.isi.edu/nsnam/ns/.
5
6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
