共查询到10条相似文献,搜索用时 93 毫秒
1.
介绍了存在于Ad Hoc网络中的隐藏和暴露终端问题,指出了解决问题的思路,并在双忙音的基础上提出了DBTMAC协议.仿真结果证明DBTMAC协议可以解决隐藏和暴露终端问题,提高网络的吞吐量,消除链路失效事件的发生. 相似文献
2.
Lloyd Errol L. Liu Rui Marathe Madhav V. Ramanathan Ram Ravi S.S. 《Mobile Networks and Applications》2005,10(1-2):19-34
Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is developed. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented. 相似文献
3.
4.
Equilibria in Topology Control Games for Ad Hoc Networks 总被引:2,自引:0,他引:2
Stephan Eidenbenz V. S. Anil Kumar Sibylle Zust 《Mobile Networks and Applications》2006,11(2):143-159
We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure
desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different
entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall
performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control
games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication
partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these
can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that
Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes
the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to
be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they
will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks.
A preliminary version of this paper appeared in DIALM-POMC ’03 [8].
Stephan Eidenbenz is a technical staff member in Discrete Simulation Sciences (CCS-5) at Los Alamos National Laboraotry. He received his Ph.D.
in Computer Science from the Swiss Federal Institute of Technology, Zurich, Switzerland in 2000. Stephan’s research covers
areas in approximability, algorithms, computational geometry, computational biology, large-scale discrete simulation, selfish
networking, efficient networking, protocol design and optimization.
V. S. Anil Kumar is currently an Assistant Professor in the Dept. of Computer Science and a Senior Research Associate at Virginia Bioinformatics
Institute, Virginia Tech. Prior to this, he was a technical staff member in Los Alamos National Laboratory. He received a
Ph.D. in Computer Science from the Indian Institute of Science in 1999. His research interests include approximation algorithms,
mobile computing, combinatorial optimization and simulation of large socio-technical systems.
Sibylle Zust received her Masters degree in mathematics from ETH Zurich in Switzerland in 2002. She wrote her diploma thesis at the University
of Copenhagen in Denmark. Sibylle Zust spent two and a half years (2002–2005) as a graduate research assistant at the Los
Alamos National Laboratory in New Mexico, USA, where she worked on algorithmic aspects of game theory and scheduling problems.
She now works for an insurance company in Zurich, Switzerland. 相似文献
5.
6.
Ad Hoc网络拓扑控制算法的研究与仿真 总被引:1,自引:0,他引:1
拓扑控制是无线网络优化的核心问题之一,其目的在于降低节点间传输功率,延长网络寿命和减少节点邻居数目。文中介绍了基于节点方向信息和基于位置信息的两种分布式算法并对其进行研究与仿真,并从业务负载量上说明拓扑控制给网络带来的显著优化。 相似文献
7.
8.
Topology control in wireless ad hoc networks is to select a subgraph of the communication graph (when all nodes use their
maximum transmission range) with some properties for energy conservation. In this paper, we propose two novel localized topology
control methods for homogeneous wireless ad hoc networks.
Our first method constructs a structure with the following attractive properties: power efficient, bounded node degree, and
planar. Its power stretch factor is at most
, and each node only has to maintain at most
neighbors where the integer
is an adjustable parameter, and β is a real constant between 2 and 5 depending on the wireless transmission environment.
It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can
be represented in
bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is
bits.
Our second method improves the degree bound to k, relaxes the theoretical power spanning ratio to
, where
is an adjustable parameter, and keeps all other properties. We show that the second structure can be constructed using at
most 3n messages, where each message has size of
bits.
We also experimentally evaluate the performance of these new energy efficient network topologies. The theoretical results
are corroborated by the simulations: these structures are more efficient in practice, compared with other known structures
used in wireless ad hoc networks and are easier to construct. In addition, the power assignment based on our new structures
shows low energy cost and small interference at each wireless node.
The work of Xiang-Yang Li is partially supported by NSFCCR-0311174.
Wen-Zhan Song received Ph.D. from Illinois Institute of Technology in 2005, BS and MS from Nanjing University of Science and Technology
in 1997 and 2000. He is currently an assistant professor in Washington State University. His current research interest is
mainly focus on network protocol and algorithm design, especially in wireless networks, sensor networks and Peer-to-Peer networks.
He is a member of the IEEE.
Yu Wang received the Ph.D. degree in computer science from Illinois Institute of Technology in 2004, the BEng degree and the MEng
degree in computer science from Tsinghua University, China, in 1998 and 2000. He has been an assistant professor of computer
science at the Univeristy of North Carolina at Charlotte since 2004. His current research interests include wireless networks,
mobile computing, algorithm design, and artificial intelligence. He is a member of the ACM, IEEE, and IEEE Communication Society.
Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He hold MS (2000)
and PhD (2001) degree at Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree
at Computer Science and Bachelor degree at Business Management from Tsinghua University, P.R. China in 1995. His research
interests span the computational geometry, wireless ad hoc networks, game theory, cryptography and network security. He is
a Member of the ACM, IEEE, and IEEE Communication Society.
Ophir Frieder is the IITRI Professor of Computer Science at the Illinois Institute of Technology. His research interests span the general
area of distributed information systems. He is a Member of ACM and a Fellow of the IEEE. 相似文献
9.
对Ad Hoc网络中两个典型的按需路由协议AODV和DSR可能受到的各种攻击进行分析,然后介绍一种认证式路出协议(ARAN),该协议在路由发现、路由建立和路由维护过程中使用数字证书和数字签名的方式进行路由信息的认证,有效防止可能受到的攻击。最后通过计算机仿真验证认证式路由协议预防攻击的性能。 相似文献
10.
Topology Management for Improving Routing and Network Performances in Mobile Ad Hoc Networks 总被引:1,自引:0,他引:1
A distributed topology management algorithm based on the construction of a forest from the topology of the network is proposed. In this algorithm, each tree of the forest forms a zone, and each zone is maintained proactively. As a result, the network can be seen as a set of non-overlapping zones. We introduce the concept of quality of connectivity for extracting the links connecting the pair of best nodes, and use this quality to construct the forest. We characterize the behaviors of the proposed topology management algorithm under various network density. We study the effect of the topology management on the performance of an ad hoc routing protocol. The results demonstrate that the performance of routing can be significantly improved with the help of topology management. 相似文献