This paper investigates the problem of finding optimal paths in single-source single-destination accumulative multi-hop networks. We consider a single source that communicates to a single destination assisted by several relays through multiple-hops. At each hop, only one node transmits, while the rest of nodes receive the transmitted signal, and store it after processing/decoding and mixing with the signals received in previous hops. This is, we consider that terminals make use of advanced energy accumulation transmission/reception techniques such us maximal ratio combining reception of repetition codes, or information accumulation with rate less codes. Accumulative techniques increase communication reliability, reduce energy consumption, and decrease latency. We investigate the properties that a routing metric must satisfy in these accumulative networks to guarantee that optimal paths can be computed with Dijkstra’s algorithm.


Click Here:-  PG Project Centers in Chennai




The work presented here builds, mainly, on top of the works conducted in We show that graphs can not model the AM network, and thus, the results derived in   for routing over graphs can not be invoked. We model the AM network by a hypergraph, and find new sufficient conditions to guarantee the optimality of Dijkstra’s algorithm in hypergraphs. We then discuss the optimality of Dijkstra’s algorithm for the minimum energy routing in static AM networks. In the case of decoded-and-forward (DF) relaying this problem has been previously addressed in DF relay nodes decode the source message completely by accumulating energy, or information from all previous transmissions. From we already know that finding the optimal transmission order for these networks is an NP complete problem.




We studied the routing problem in accumulative multi-hop networks. We showed that as opposed to traditional multi-hoping where the network is well modeled by graph, for routing in accumulative networks, the network needs to be modeled by a hyper graph. We studied the properties that guarantee that Dijkstra’s algorithm finds the optimal path in such networks, and presented sufficient conditions for the optimality. These conditions are particularized for the minimum energy routing problem with decode-and-forward relays and for the cut-set bound.





  • System                             : Pentium IV 2.4 GHz.
  • Hard Disk                          : 40 GB.
  • Floppy Drive                      : 1.44 Mb.
  • Monitor                             : 15 VGA Colour.
  • Mouse                               : Logitech.
  • Ram                                 : 2 Gb.




  • Operating system        : Windows XP/7.
  • Coding Language         :,
  • Tool                            : Visual Studio 2010
  • Database                     : SQL SERVER 2008




[1] J. Sobrinho, “An algebraic theory of dynamic network routing,” Net- working, IEEE/ACM Transactions on, vol. 13, no. 5, pp. 1160 – 1173, oct. 2005.

[2] Y. Yang and J. Wang, “Design guidelines for routing metrics in multihop wireless networks,” in IEEE INFOCOM, 2008, pp. 1615 –1623.

[3] I. Maric and R. Yates, “Cooperative multihop broadcast for wireless networks,” IEEE J. Select. Areas Commun., vol. 22, no. 6, pp. 1080– 1088, Aug. 2004.

[4] J. Chen, L. Jia, X. Liu, G. Noubir, and R. Sundaram, “Minimum energy accumulative routing in wireless networks,” in Proc. IEEE INFOCOM, vol. 3, Mar. 2005, pp. 1875 – 1886.

[5] A. Molisch, N. Mehta, J. Yedidia, and J. Zhang, “Cooperative relay networks using fountain codes,” in Proc. IEEE Global Communications Conference (GLOBECOM), Nov. 2006.

Leave a comment