中文模板

Size: px

Start display at page:

Download "中文模板"

瑞昝
5 years ago
Views:

1 ISSN CODEN RUXUEW Journal of Software Vol18 No6 June 27 pp DOI: 1136/jos18138 Tel/Fax: by Journal of Software All rights reserved Ad Hoc ( ) 7171) 2 ( 7171) Distributed Topology Control Algorithm for Ad Hoc Networks Using Directional Antennas HE Peng 12+ LI Jian-Dong 12 CHEN Yan-Hui 12 CHEN Liang 12 1 (State Key Laboratory of Integrated Service Networks (Xidian University) Xi an 7171 China) 2 (Broadband Wireless Communications Laboratory Information Science Institute Xidian University Xi an 7171 China) + Corresponding author: Phn: ext 85 Fax: phe@mailxidianeducn He P Li JD Chen YH Chen L Distributed topology control algorithm for ad hoc networks using directional antennas Journal of Software 2718(6): Abstract: A distributed topology control algorithm for ad hoc networks with directional antennas is proposed in this paper The topology is controlled not only by adjusting the transmission powers of nodes but also by changing the antenna s pattern (direction) A node grows its transmission power until it finds some neighbor nodes in every sector of its directional antenna Two planarized optimizations that further reduce some redundant edges are employed and make the topology as a planar graph eventually The resulting network topology increases network lifetime by reducing transmission power and decreases traffic interference by having low node degrees Simulation results demonstrate the effectiveness of the proposed algorithm Key words: : topology control; directional antennas; planar graph; wireless ad hoc networks : ; ; ad hoc Supported by the Key Project of National Natural Science Foundation of China under Grant No ( ); the National Natural Science Foundation of China and the Foundation of Microsoft Research Institute in Asia under Grant No ( ); the National High-Tech Research and Development Plan of China under Grant No25AA12391 ( (863)); the National Grand Fundamental Research Program of Education of China under Grant No14171 ( ); the Foundation of Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institute of China ( ) Received ; Accepted

2 :Ad Hoc 139 : TP393 : A Ad Hoc Internet Ad Hoc ( ) Ad Hoc Ad Hoc [1] [2] [3] [4] CONNEC [5] MINR [6] Ad Hoc LINT [5] LMST [2] CONPOW [7] GPS Hello CBTC [8] Hello AOA(angle-of-arrival) [9] Ad Hoc (AOA) [1] (directional antenna-based topology control) CBTC SOA(sector-of-arrival) Ad Hoc 1 Ad Hoc ID u N u p(u) p(u) p(u) max p(u) max u P max GPS ( GPS ) β [11] β 2β (free space) β=2 P t P r 2 PG t tgrλ Pr = 2 ( 4πd ) L G t G r λ d (two-ray) β=4 P t P r 2 2 PG t tgrht hr Pr = (2) 4 d (1)

3 131 Journal of Software Vol18 No6 June 27 h t h r u v d(uv) u v p(uv)=td(uv) β p(uv)=p(vu) Ad Hoc 1 R max R max 2 DIST(uv) 3 uν u v 4 G R max V(G ) G E(G ) G uv E(G ) u v DIST(uv) R max G 5 N(u) u 1 u G 6 u u d(u) 7 G E uv E(G E ) u v DIST(u v) r(u) r(u) u r(u) [R max ] V(G E )= V(G )E(G E ) E(G ) 8 N E (u) u G E 1 u 1 v N E (u) DIST(uv) r(u) N E (u) N(u) 9 G G 2 () Ad Hoc ( ) Ad Hoc N 2π/N k (1 k N) : u 1 N E (u) u p(u) Hello Hello u ID u p(u) v u Hello u ACK ACK v ID v p(v) uv u v v N E (u) u N E (v) u p(u) v p(v) p(u) p(uv) p(v) p(uv) v u v N E (u) u v (SOA) G E 21 (1) u p(u)=ε (2) u N ( u 1 ) (3) u Hello ACK u v u v N E (u) u v (4) (3) u u p(u)=p(u) max

4 :Ad Hoc // Basic algorithm on node u Current_Pow=Init_Min_Pow; N E (u)= Total_Sec(u)=NULL; Emp_Sec(u)=Total_Sec(u); while (Emp_Sec(u)==NULL && Current_Pow<=Max_Pow) Broadcast(up); /* Node u broadcasts a Hello message to N sectors with the initial minimum transmission Power */ Gather(uvp ACK ); /* Gather ACK sending by node v */ for (every node v sending the ACK ) If (v is not in N E (u)) N E (u)=n E (u) {v}; Emp_Sec(u)=The rest of sectors that are not covered by any node in N E (u) end if Current_Pow=IncreasePow(Current_Pow); end for end while 22 [3] [4] 221 (1) u 1 (2) u N E (u) (3) N E (u) v DIST(uv) w N E (u) u proposal(uv) G E uv u (4) v proposal(uv) v u 1 N E (v) v uv accept(uv); v reject(uv) (5) u v accept(uv) G E uv v 222 (1) u 1 (2) u N E (u) (3) N E (u) v u v DIST(uv) w N E (u) u proposal(uv) G E uv u (4) v proposal(uv) v u 1 N E (v) v uv accept(uv); v reject(uv) (5) u v accept(uv) G E uν v I 2 3

5 1312 Journal of Software Vol18 No6 June 27 2 /* algorithm on node u the basic part of is the same as and we add some optimizations as follows */ m=midpoint of uv end for for all v N E (u) do for all w N E (u) do end for if w==v then continue else if DIST(mw)<DIST(um) then eliminate edge uv break end if 3 I /* I algorithm on node u the basic part of I is the same as and we add some optimizations as follows */ // Optimizations for all v N E (u) do for all w N E (u) do if w==v then continue else if DIST(uv)>max(DIST(uw);DIST(vw)) then eliminate edge uv break end if end for end for 3 I 3 AODV [12] m 2 25m 5~3 N=6 π/3 β 4 db 15m 94dBW 1dBW~1dBW 35m~25m NS (network simulator) : 1 1 1m 2 Random Waypoint 8211 [13] MAC

6 :Ad Hoc 1313 DCF RTS CTS MAC CSMA/CD 9s 1 CBR : CBR 1ms~1ms 512 4Kb/s~4Kb/s 32 d(u) 3 I : (maximum degree) (average degree) (average transmission radius) (a) 25m 1(b)~ 1(d) 1(c) 1(d) (a) Without topology control (a) (b) algorithm (b) Fig1 (c) algorithm (c) (d) I algorithm (d) I Network topology obtained by different topology control algorithm I 3(a) 3(b) 8

1314 Journal of Software Vol18 No6 June 27 Average node degree 6 5 4 3 2 1 I 5 1 15 2 25 3 Fig2 Comparison of and

maximum node degree (a) Fig3 Average max node degree 9 8 7 6 5 4 3 2 1 I 5 1 15 2 25 3 (b) Largest maximum node

7 1314 Journal of Software Vol18 No6 June 27 Average node degree I Fig2 Comparison of and I with respect to average node degree 2 I Average max node degree I (a) Average maximum node degree (a) Fig3 Average max node degree I (b) Largest maximum node degree (b) Comparison of and I with respect to maximum node degree 3 I 4(a) 4(b) I 5 5 I 55% 2 3% 33 AODV [12] 3 CBR :1 1 1

:Ad Hoc 1315 Average radius (m) 3 28 25 2 15 1 Fig4 5 Node I 5 1 15 2 25 3 (a) Node average transmission radius

radius (b) Comparison of and I with respect to the radius 4 I Fig5 Expended energy ratio 1 9 8 7 6 5 4 3 2 1 I 5

simulation 1 Number of nodes 1 Maximum transmission range (m) 25 Rate of channel (Mbit/s) 2 Region (m 2 ) 1 1

8 :Ad Hoc 1315 Average radius (m) Fig4 5 Node I (a) Node average transmission radius (a) Average max radius (m) Node I (b) Node average maximum transmission radius (b) Comparison of and I with respect to the radius 4 I Fig5 Expended energy ratio I Comparison of NONE and I with respect to the expended energy ratio (EER) 5 I Table 1 Parameters of simulation 1 Number of nodes 1 Maximum transmission range (m) 25 Rate of channel (Mbit/s) 2 Region (m 2 ) 1 1 Type of traffic CBR CBR flows 1 Packet arrival interval (ms) 1~1 Length of packet (Byte) 512 Simulation time (s) (a) 1 1

1316 Journal of Software Vol18 No6 June 27 6(b) 1 1 1Kb/s MAC 6(c) Fraction data Pks

12 9 6 3 I 5 1 15 2 25 3 35 4 Traffic load per flow (Kb/s) (a) Fraction data Pks delivered

14 12 1 8 6 4 I 5 1 15 2 25 3 35 Traffic load per flow (Kb/s) (c) Average throughput (c)

9 1316 Journal of Software Vol18 No6 June 27 6(b) 1 1 1Kb/s MAC 6(c) Fraction data Pks delivered I Traffic load per flow (Kb/s) End to end delay (s) I Traffic load per flow (Kb/s) (a) Fraction data Pks delivered (a) (b) Average end-to-end delay (b) Fig6 Average throughput per flow I Traffic load per flow (Kb/s) (c) Average throughput (c) Performance obtained from one-hop CBR flows at various loads CBR 1 AODV [12] 7(a) ; 7(b) ;

:Ad Hoc 1317 MAC End-to-End delay (s) 15 1 5 I 1 2 3 4 Traffic load per flow (Kb/s) (a) Average end-to-end delay (a) Fig7 Average throughput per flow (Kb/s) 24 2 16 12 8 I 4 1 2 3 4 Traffic load per

network protocols for wireless networks Wireless Networks 217(4):343 358 [2] Li N Hou JC Sha L Design and analysis of an MST based topology control algorithm IEEE Trans on Wireless Communications

10 :Ad Hoc 1317 MAC End-to-End delay (s) I Traffic load per flow (Kb/s) (a) Average end-to-end delay (a) Fig7 Average throughput per flow (Kb/s) I Traffic load per flow (Kb/s) (b) Average throughput (b) Performance obtained from multi-hop CBR flows at various loads 7 4 MAC References: [1] Jones CE Sivalingam KM Agrawal P Chen JC A survey of energy efficient network protocols for wireless networks Wireless Networks 217(4): [2] Li N Hou JC Sha L Design and analysis of an MST based topology control algorithm IEEE Trans on Wireless Communications 254(3): [3] Santi P Blough DM Vainstein F A probabilistic analysis for the range assignment problem in ad hoc networks In: Lee SJ ed Proc of the ACM Symp on Mobile Ad Hoc Networking and Computing New York: ACM Press [4] Gupta P Kumar PR The capacity of wireless networks IEEE Trans on Information Theory 246(2): [5] Ramanathan R Rosales-Hain R Topology control of multihop wireless networks using transmit power adjustment In: Irene K Yuval S eds Proc of the 19th Annual Joint Conf of the IEEE Computer and Communications Societies Tel Aviv: IEEE Press [6] EstheR J Clayton O Topology control for efficient information dissemination in ad hoc networks In: Mohammad SO ed Proc of the Int l Symp on Performance Evaluation of Computer and Telecommunication Systems San Diego: Soc for Modeling and Simulation Int l

11 1318 Journal of Software Vol18 No6 June 27 [7] Narayanaswamy S Kawadia V Sreenivas RS Kumar PR Power control in ad-hoc networks: Theory architecture algorithm and implementation of the COMPOW protocol In: Luciano L ed Proc of the European Wireless Conf Next Generation Wireless Networks: Technologies Protocols Services and Application Florence: EW Press [8] Li L Halpern J Bahl V Wang YM Wattenhofer R Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks In: Mark T Dave D eds Proc of the 2th ACM Symp on Principle of Distributed Computing (PODC) New York: ACM Press [9] Krizman K Biedka TE Rappaport TS Wireless position location: Fundamentals implementation strategies and source of error In: Eric S ed Proc of the 47th IEEE Vehicular Technology Conf Phoenix: IEEE Operation Center [1] Huang ZC Zhang ZS Ryu B Power control for directional antenna-based mobile ad hoc networks In: Clifford J King R eds Proc of the 26 Int l Conf Communications and Mobile Computing New York: ACM Press [11] Rodoplu V Meng TH Minimum energy mobile wireless networks IEEE Journal on Selected Areas in Communications (8): [12] Perkins CE Royer EM Ad-Hoc on demand distance vector routing In: Kristine K ed Proc of the 2nd Workshop on Mobile Computing Systems and Applications New Orleans: IEEE Computer Society [13] IEEE 8211 Wireless LAN medium access control (MAC) and physical layer (PHY) Specifications 1999 (1975 ) (1972 ) (1962 ) IP Ad Hoc (1979 ) Ad Hoc

Microsoft PowerPoint - Aqua-Sim.pptx

Microsoft PowerPoint - Aqua-Sim.pptx Peng Xie, Zhong Zhou, Zheng Peng, Hai Yan, Tiansi Hu, Jun-Hong Cui, Zhijie Shi, Yunsi Fei, Shengli Zhou Underwater Sensor Network Lab 1 Outline Motivations System Overview Aqua-Sim Components Experimental