Minimum
Cost Blocking Problem in Multi-path Wireless Routing Protocols
ABSTRACT:
We present a class of Minimum Cost
Blocking (MCB) problems in Wireless Mesh Networks (WMNs) with multi-path wireless
routing protocols. We establish the provable superiority of multi-path routing
protocols over conventional protocols against blocking, node-isolation and
network-partitioning type attacks. In our attack model, an adversary is
considered successful if he is able to capture/isolate a subset of nodes such
that no more than a certain amount of traffic from source nodes reaches the
gateways. Two scenarios, viz. (a) low mobility for network nodes, and (b) high
degree of node mobility, are evaluated. Scenario (a) is proven to be NP-hard
and scenario (b) is proven to be #P-hard for the adversary to realize the goal.
Further, several approximation algorithms are presented which show that even in
the best case scenario it is at least exponentially hard for the adversary to
optimally succeed in such blocking-type attacks. These results are verified
through simulations which demonstrate the robustness of multi-path routing protocols
against such attacks. To the best of our knowledge, this is the first work that
theoretically evaluates the attack-resiliency and performance of multi-path
protocols with network node mobility.
EXISTING SYSTEM:
MULTI-PATH traffic scheduling and routing protocols in
wired networks are deemed superior over conventional single path protocols in
terms of both enhanced throughput and robustness. In wireless networks, even
though the dynamic nature of networks and resource constraints entail
additional overhead in maintaining and reconfiguring multiple routes, which
could offset the benefits seen in wired networks, research has proven that
multi-path routing provides better Quality of Service (QoS) guarantees.
DISADVANTAGES
OF EXISTING SYSTEM:
Blocking, node-isolation and network-partitioning
type attacks are easy to launch and are effective in the wireless networks
domain due to channel constraints and dynamic network topologies
PROPOSED SYSTEM:
• The identification of the Minimum
Cost Blocking (MCB) problem. Though we consider MCB in the WMN setting, the
problem is applicable to other wireless or wired networks.
• Evaluating the hardness of the problem.
MCB is NPhard for the low/no node mobility scenario and #P-hard for networks with patterned
node mobility. The reduction for
no-mobility is derived from the basic Set Cover problem and for mobility scenario,
from the 3SAT and #SAT
problems.
• Development of approximation
algorithms for the best case scenario and the performance testing of these
algorithms in different settings through random graphs based experiments.
• Laying direction for future research
to evaluate the performance of multi-path protocols against sophisticated attacks
in mobile wireless networks.
ADVANTAGES
OF PROPOSED SYSTEM:
Our proposed system demonstrates the superiority of
multi-path protocols over traditional single-path protocols in terms of
resiliency against blocking and node isolation-type attacks, especially in the
wireless networks domain. Multi-path protocols for WMNs make it extremely hard for
an adversary to efficiently launch such attacks.
SYSTEM CONFIGURATION:-
HARDWARE CONFIGURATION:-
ü Processor - Pentium –IV
ü Speed - 1.1
Ghz
ü RAM - 256
MB(min)
ü Hard Disk -
20 GB
ü Key Board -
Standard Windows Keyboard
ü Mouse - Two
or Three Button Mouse
ü Monitor - SVGA
SOFTWARE CONFIGURATION:-
ü Operating System : Windows XP
ü Programming Language :
JAVA
ü Java Version :
JDK 1.6 & above.
REFERENCE:
Qi Duan, Mohit Virendra, Shambhu
Upadhyaya, Senior Member, IEEE, Ameya Sanzgiri, “Minimum Cost Blocking
Problem in Multi-path Wireless Routing Protocols”, IEEE TRANSACTIONS ON COMPUTERS, VOL. X, NO. X, FEBRUARY 2013.