微信服务号

微信订阅号

2025-5-16- 8
Home > Archive>Volume 25, Issue 6, 2014 >1291-1300. DOI:10.13328/j.cnki.jos.004434
PDF HTML XML Export Cite reminder
Optimal Stopping Decision Method for Routing of Opportunistic Networks
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [18]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Delivery delay is an important performance metric in opportunistic networks. With given buffer size and copy numbers, how to select appropriate nodes to replicate message is the key to minimizing delivery delay. To solve this problem, this paper proposes an optimal stopping decision method for routing opportunistic networks (OSDR). With OSDR, the average meeting time between a node and the destination is regarded as the forwarding utility of the node. A node carrying a message observes the random forwarding utilities of the nodes it meets, and replicates messages according to the optimal stopping rule, which turns out to be threshold-based. By making tradeoffs between the forwarding utility and waiting cost, OSDR achieves the minimum delivery delay expectation. This paper introduces the OSDR network model and existence proof and calculation of optimal stopping rule in detail. Simulation results show that OSDR outperforms other protocols in delivery delay and delivery rate.

    Reference
    [1] Pelusi L, Passarella A, Conti M. Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks. IEEE Communications Magazine, 2006,44(11):134-141. [doi: 10.1109/MCOM.2006.248176]
    [2] Vadhat A, Becker D. Epidemic routing for partially connected ad hoc networks. Technical Report, CS-2000-06, Durham, North Carolina: Duke University, 2000. 1-16.
    [3] Spyropoulos T, Psounis K, Raghavendra CS. Spray and wait: An efficient routing scheme for intermittently connected mobile networks. In: Guérin R, ed. Proc. of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. Philadelphia: ACM Press, 2005. 252-259. [doi: 10.1145/1080139.1080143]
    [4] Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks. Mobile Computing and Communications Review, 2003,7(3):19-20. [doi: 10.1145/961268.961272]
    [5] Ferguson TS. Optimal stopping and applications 2006. 2006. http://www.math.ucla.edu/~tom/Stopping/Contents.html
    [6] Helsinki University of Technology. The opportunistic network environment simulator 2012. 2012. http://www.netlab.tkk.fi/tutkimus/dtn/theone/[7] Exploratorium. Cabspotting project 2012. 2012. http://cabspotting.org/index.html/[8] Spryropoulos T, Psounis K, Raghavendra CS. Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated
    mobility. In: Hurson A, Pingali G, eds. Proc. of the 5th Annual IEEE Int'l Conf. on Pervasive Computing and Communications Workshops (PerComW 2007). New York: IEEE, 2008. 79-85. [doi: 10.1109/PERCOMW.2007.108]
    [9] Liu C, Wu J. An optimal probabilistic forwarding protocol in delay tolerant networks. In: Knightly EW, ed. Proc. of the 10th ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc 2009). New York: ACM Press, 2008. 105-114. [doi: 10.
    1145/1530748.1530763]
    [10] Balasubramanian A, Levine BN, Venkataramani A. DTN routing as a resource allocation problem. In: Murai J, ed. Proc. of the Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2007). Kyoto:ACM Pewss, 2007. 373-384. [doi: 10.1145/1282380.1282422]
    [11] Cai H, Eun DY. Crossing over the bounded domain: From exponential to power-law intermeeting time in mobile ad hoc networks.IEEE/ACM Trans. on Networking, 2009,17(5):1578-1591. [doi: 10.1109/TNET.2008.2011734]
    [12] Hui P, Crowcroft J, Yoneki E. Bubble rap: Social-Based forwarding in delay tolerant networks. IEEE Trans. on Mobile Computing,2011,10(11):1576-1589. [doi: 10.1109/TMC.2010.246]
    [13] Gao W, Li Q, Zhao B, Cao G. Multicasting in delay tolerant networks: A social network perspective. In: Knightly EW, ed. Proc. of the 10th ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc 2009). New Orleans, 2009. 299-308. [doi: 10. 1145/1530748.1530790]
    [14] Altmana E, Basar T, Pellegrini FD. Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks. Performance
    Evaluation, 2010,67(4):299-317. [doi: 10.1016/j.peva.2009.09.001]
    [15] Erramilli V, Crovella M, Chaintreau A, Diot C. Delegation forwarding. In: Jia X, ed. Proc. of the 9th ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc 2008). Hong Kong: ACM Press, 2008. 251-260. [doi: 10.1145/1374618.1374653]
    [16] Hanbali AA, Nain P, Altman E. Performace of ad hoc networks with two-hop relay routing and limited packet lifetime. Performance Evaluation (extended versiton), 2008,65(6-7):463-483. [doi: 10.1016/j.peva.2007.12.005]
    [17] Cai S, Zhang SF, Dong YQ, Wu GX. An optimal stopping strategy for opportunistic broadcast channel access. Ruan Jian Xue Bao/Journal of Software, 2012,23(9):2413-2428 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4138.htm [doi: 10.3724/SP.J.1001.2012.04138]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张三峰,黄迪,陈州,吴国新.一种面向机会网络路由的最优停止决策方法.软件学报,2014,25(6):1291-1300

Copy
Share
Article Metrics
  • Abstract:4236
  • PDF: 5937
  • HTML: 1306
  • Cited by: 0
History
  • Received:October 11,2012
  • Revised:January 07,2013
  • Online: November 04,2013
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044877Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063