MANET MANET MANET (DTN: Delay Tolerant Network) DTN DTN DTN DTN [7], [3], [11] [8] % N M m M n N D(m, n) Size(m) m MD(m) m M, n N, MD(m) = max{d

Size: px

Start display at page:

Download "MANET MANET MANET (DTN: Delay Tolerant Network) DTN DTN DTN DTN [7], [3], [11] [8] % N M m M n N D(m, n) Size(m) m MD(m) m M, n N, MD(m) = max{d"

みいかねぎたや
5 years ago
Views:

1 DEIM Forum 2013 F1-4 DTN, DTN (DTN ) DTN 20% DTN Study of the message forwarding order scheduling methods for delivery delay reduction of broadcast in Delay Tolerant Network Yusuke SAWAMURA, Yuichi TERANISHI,, Kaname HARUMOTO, and Shojiro NISHIO Graduate School of Information Science and Technology, Osaka University 1-5 Yamada, Suita, Osaka Japan Cybermedia Center, Osaka University Mihogaoka 5 1, Suita-shi, Osaka Japan National Institute of Information and Communication Technology Nukuikitamati, Koganei, Tokyo Japan Graduate School of Engineering, Osaka University, Osaka University 2-1 Yamada, Suita, Osaka Japan {sawamura.yusuke,nishio}@ist.osaka-u.ac.jp, teranisi@cmc.osaka-u.ac.jp, harumoto@eng.osaka-u.ac.jp 1. PC Bluetooth WiFi (MANET) MANET

2 MANET MANET MANET (DTN: Delay Tolerant Network) DTN DTN DTN DTN [7], [3], [11] [8] % N M m M n N D(m, n) Size(m) m MD(m) m M, n N, MD(m) = max{d(m, n)} (1) m MD(m) l M, AD(M) = max{md(l)} < (2)

3 AD(M) E(M) E(M) E(M) = X X D(m, n) (3) n N m M R[m] C c C B(c) c n 1, n 2 N Diff(n 1, n 2, c) Epidemic Routing X Size(m) < X B(c) (4) m M c C c, X Size(m) > B(c) (5) m Diff(n1,n2,c) minimize E(M), AD(M) subject to (2)(4)(5) (6) DTN +5& -5& :/& +.34-=& :.& +,34-5& +.& -.& +/& -/& :<& +,3-9& +5& -5& +.& -.& +,34-<& :,& :9& :;& +9& -9&!"#$%012&!"#$%67812)*& 12CHI!"#$%J)*& >)*-?@?ABCDEFGD)*& 1 FCFO 3. [6], [5], [4] DTN [7], [3], [11] FCFO (First Created First Out) 1 1 M1 3 M2 1 M2 M2 2 M2 [1]

4 [8] i g(i) DTN 99 ESF (Estimated Slowest First) ESF ESF PID MAC GPS ID ESF +5& -5& :/& +.34-=& :.& +,34-5& +.& -.& +/& -/& :<& +,3-9& +5& -5& +.& -.& +.34-<& :,& :9& +,34-,K& :;& +9& -9&!"#$%012&!"#$%67812)*& 12CHI!"#$%J)*& >)*-?@?ABCDEFGD)*& 2 ESF ESF 2 ESF N1 2 M1 M2 3 M1 2 M ESF 4. 3 ESF ESF ID

5 hi) bi4jk"#$%&'() cd/34e67fg) *+,-.BUV)!"#$%&'() *+,-./01) CDEAFGHI4JKL,-./MNBOPQ) /,-.(RS) T,-.GHUVJK) OPWXYZ[8) \<]A^B_`J9345a-) ) N m M s(m) h(m) h(m) = X n N f(m, n) (8) 8 < 0 (m SV T (n)) f(m, n) = : 1 (m / SV T (n)) C el (m) C el (m) = h(m) + s(m) N (9) (10) C el (m)(0 < i < n) 3 ESF C e (m) = E(C el (m)) (11) 1 ID ID A B C D A 2 3 B 2 C m V e (m) C e (m) T e (m) m V e(m) = Ce(m) T e(m) C el (m) SVT(n) n SMT(m) 2, 1 (7) 2, /3 2 C A B / ESF DTN OneSimulator [2] ,

6 3 10[m] 30kbps 4400[s] 2100[s] Sm[] Im[s/ ] [0, 0]s Sa[m/ ] 160 Zipf s.,.,. Zipf [9] Zipf Web Zipf k N s s f(k; s, N) = 1/k s P N n=1 1/ns (12) ID 128 ID SHA ID Average delay % % 99 percentile of 100% delivery delay 5. 3 m T e(m) FCFO (First Created Fist Out) m s m s = arg max T e(m) (13) m M OSF (Optimized Slowest First) D(m) m s m s = arg min m M D(m) T e (m) (14) RS (Random Selection) m s , 6 99 Mobireal [10] [K ] Zipf [] 5 6 ESF 90% RS 90% RS

7 Zipf S 8 Zipf S Mobireal Mobireal 99 RS 50% 90% 90% 70% 80%OSF 10% Zipf 30K 0.5[ / ] 1.0[m/ ] 7, 8 S RS LCFO 99 FCFO OSF ESF 99

8 OSF ESF FCFO 10 RS FCFO ESF OSF 5. 7 Mobireal [10] RWP ESF 99 RS [1] H. Gong and J. Kim. A prioritization-based applicationoriented broadcast protocol for delay-tolerant networks. In Wireless Communications and Networking Conference, WCNC IEEE, pp. 1 6, april [2] A. Keränen, J. Ott, and T. Kärkkäinen. The one simulator for dtn protocol evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques, Simutools 09, pp. 55:1 55:10, ICST, Brussels, Belgium, Belgium, ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). [3] A. Khelil, P. J. Marrn, C. Becker, and K. Rothermel. Hypergossiping: A generalized broadcast strategy for mobile ad hoc networks. Ad Hoc Networks, 5(5): , [4] A. Khelil and N. Suri. Gossiping: Adaptive and reliable broadcasting in manets. In A. Bondavalli, F. Brasileiro, and S. Rajsbaum eds., Dependable Computing, Vol of Lecture Notes in Computer Science, pp Springer Berlin Heidelberg, [5] A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying for flooding broadcast messages in mobile wireless networks. In System Sciences, HICSS. Proceedings of the 35th Annual Hawaii International Conference on, pp , jan [6] Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. In Wireless Communications and Networking, WCNC IEEE, Vol. 2, pp vol.2, march [7] A. Vahdat and D. Becker. Epidemic routing for partiallyconnected ad hoc networks [8] Y. Wang and J. Wu. Ticket-based multiple packet broadcasting in delay tolerant networks. Ad hoc and Sensor Wireless Networks, April [9] G. Zipf. Human behaviour and the principle of least-effort. Addison-Wesley, Cambridge, MA, [10],,. mobireal., 10: , [11],,,, , 2011, pp , jun OSF 99 10% UDP Mac

1 Web DTN DTN 2. 2 DTN DTN Epidemic [5] Spray and Wait [6] DTN Android Twitter [7] 2 2 DTN 10km 50m % %Epidemic 99% 13.4% 10km DTN [8] 2

1 Web DTN DTN 2. 2 DTN DTN Epidemic [5] Spray and Wait [6] DTN Android Twitter [7] 2 2 DTN 10km 50m % %Epidemic 99% 13.4% 10km DTN [8] 2 DEIM Forum 2014 E7-1 Web DTN 112 8610 2-1-1 UCLA Computer Science Department 3803 Boelter Hall, Los Angeles, CA 90095-1596, USA E-mail: yuka@ogl.is.ocha.ac.jp, mineo@cs.ucla.edu, oguchi@computer.org Web