DEIM Forum 2013 F1-4 DTN, 565-0871 1-5 567-0047 5-1 184-8795 4-2-1 565-0871 2-1 E-mail: {sawamura.yusuke,nishio}@ist.osaka-u.ac.jp, teranisi@cmc.osaka-u.ac.jp, harumoto@eng.osaka-u.ac.jp 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 565-871 Japan Cybermedia Center, Osaka University Mihogaoka 5 1, Suita-shi, Osaka 567 0047 Japan National Institute of Information and Communication Technology 4-2-1 Nukuikitamati, Koganei, Tokyo 184-8795 Japan Graduate School of Engineering, Osaka University, Osaka University 2-1 Yamada, Suita, Osaka 565-0871 Japan E-mail: {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
MANET MANET MANET (DTN: Delay Tolerant Network) DTN DTN DTN DTN [7], [3], [11] [8] 2. 100% 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)
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]
[8] i g(i) 4. 4. 1 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 M2 2 4. 2 ESF 4. 3 ESF ESF 3 4. 3. 1 ID
hi) bi4jk"#$%&'() cd/34e67fg) *+,-.BUV)!"#$%&'() *+,-./01) CDEAFGHI4JKL,-./MNBOPQ) /,-.(RS) T,-.GHUVJK) OPWXYZ[8) \<]A^B_`J9345a-) 23456789) 0:6;<=>?/@A'B01) 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 4. 3. 4 (9) (10) C el (m)(0 < i < n) 3 ESF C e (m) = E(C el (m)) (11) 1 ID 1 2 3 2 ID A B C D A 2 3 B 2 C 4 4. 3. 2 m V e (m) C e (m) T e (m) m V e(m) = Ce(m) T e(m) 4. 3. 3 C el (m) SVT(n) n SMT(m) 2, 1 (7) 2, 1 3 2 2/3 2 C A B 1 3 1 2/3 4. 3. 5 5. ESF DTN OneSimulator [2] 5. 1 3,
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 32 5. 2 Average delay 99 100% 99 4 4 99 99% 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 5. 4 99 5, 6 99 Mobireal [10] 4 4 30[K ] Zipf 1.5 160[] 5 6 ESF 90% RS 90% RS
5 6 99 7 Zipf S 8 Zipf S 99 9 10 99 11 Mobireal 12 99 Mobireal 99 RS 50% 90% 90% 70% 80%OSF 10% 99 5. 5 Zipf 30K 0.5[ / ] 1.0[m/ ] 7, 8 S RS LCFO 99 FCFO OSF ESF 99
5. 6 9 OSF ESF FCFO 10 RS FCFO ESF OSF 5. 7 Mobireal [10] 11 12 RWP 6. 5. ESF 99 RS 13 99 50 [1] H. Gong and J. Kim. A prioritization-based applicationoriented broadcast protocol for delay-tolerant networks. In Wireless Communications and Networking Conference, 2009. WCNC 2009. IEEE, pp. 1 6, april 2009. [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, 2009. 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):531 546, 2007. [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. 4746 of Lecture Notes in Computer Science, pp. 123 141. Springer Berlin Heidelberg, 2007. [5] A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying for flooding broadcast messages in mobile wireless networks. In System Sciences, 2002. HICSS. Proceedings of the 35th Annual Hawaii International Conference on, pp. 3866 3875, jan. 2002. [6] Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. In Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE, Vol. 2, pp. 1124 1130 vol.2, march 2003. [7] A. Vahdat and D. Becker. Epidemic routing for partiallyconnected ad hoc networks. 2000. [8] Y. Wang and J. Wu. Ticket-based multiple packet broadcasting in delay tolerant networks. Ad hoc and Sensor Wireless Networks, April 2012. [9] G. Zipf. Human behaviour and the principle of least-effort. Addison-Wesley, Cambridge, MA, 1949. [10],,. mobireal., 10:117 125, 2004. [11],,,,.. 2011, 2011, pp. 1121 1129, jun 2011. 7. OSF 99 10% UDP Mac