Outline

  • Abstract
  • Keywords
  • 1. Introduction
  • 2. Problem Formulation
  • 3. Design of Ga for Dncp
  • 3.1. the Basic Idea of Gas
  • 3.2. Chromosome Structure
  • 3.3. Evolutionary Operators
  • 3.4. Heuristic Rules
  • 4. Simulation Results
  • 4.1. the Setup of the Experiments
  • 4.2. the Experimental Results of Sncp
  • 4.3. the Experimental Results of Dncp
  • 4.4. Further Analysis of Rule 4 and Rule 5
  • 4.5. the Influence of Field Size on the Performance of Our New Gas
  • 5. Conclusions and Future Work
  • Acknowledgements
  • Appendix: Definitions of Terms and Notations
  • References

رئوس مطالب

  • چکیده
  • کلیدواژه ها
  • 1. مقدمه
  • 2 شکل گیری (فرمولاسیون مسئله)
  • 3. طراحی GA برای DNCP
  • 3.1 ایده ی اصلی Gas
  • 3.2 ساختار کروموزومی
  • 3.3 اپراتورهای تکوینی
  • 3.4 قوانین ابتکاری
  • 4. نتایج شبیه سازی
  • 4.2 نتایج آزمایشی SNCP
  • 4.3 نتایج آزمایشی DNCP
  • 4.4 تحلیل بیشتر قانون 4 و 5
  • 4.5 تاثیر اندازه ی میدان بر روی عملکرد GAs جدیدما
  • 5. نتیجه گیری ها و کار آینده

Abstract

The network coding problem (NCP), which aims to minimize network coding resources such as nodes and links, is a relatively new application of genetic algorithms (GAs) and hence little work has so far been reported in this area. Most of the existing literature on NCP has concentrated primarily on the static network coding problem (SNCP). There is a common assumption in work to date that a target rate is always achievable at every sink as long as coding is allowed at all nodes. In most real-world networks, such as wireless networks, any link could be disconnected at any time. This implies that every time a change occurs in the network topology, a new target rate must be determined. The SNCP software implementation then has to be re-run to try to optimize the coding based on the new target rate. In contrast, the GA proposed in this paper is designed with the dynamic network coding problem (DNCP) as the major concern. To this end, a more general formulation of the NCP is described. The new NCP model considers not only the minimization of network coding resources but also the maximization of the rate actually achieved at sinks. This is particularly important to the DNCP, where the target rate may become unachievable due to network topology changes. Based on the new NCP model, an effective GA is designed by integrating selected new problem-specific heuristic rules into the evolutionary process in order to better diversify chromosomes. In dynamic environments, the new GA does not need to recalculate target rate and also exhibits some degree of robustness against network topology changes. Comparative experiments on both SNCP and DNCP illustrate the effectiveness of our new model and algorithm.

Keywords: - - -

Conclusions

As a relatively new information theory, network coding has already demonstrated a significant influence on many research areas such as communication systems, network protocol, wireless networks, and network security. The optimization of network coding, which aims to minimize network coding resources such as coding nodes and links, has recently attracted research attention, with efforts to date focused mainly on the static network coding problem (SNCP). This paper has considered how to address the dynamic network coding problem (DNCP) by proposing its general formulation, and then developing an effective Genetic Algorithm (GA) to realize it. The new model proposed in this paper discards the popular assumption that a target rate is always achievable as long as all nodes allow coding, and introduces the actually achieved rate at sinks, along with the target rate and required resources, to the objective function in order to optimize the system. In order to derive the rate actually achieved, the GA reported is designed based on a new chromosome structure, which allows each chromosome to record a specific network protocol and coding scheme. As a result, the information flow on links can be checked at any stage of optimization. The new representation also makes evolutionary operations free of feasibility problems, and makes it easy to integrate some useful problem-specific heuristic rules into the algorithm. The effectiveness of the new model and GA is illustrated by simulations of both the SNCP and the DNCP.

There are several directions for future research so that the NCP models and the GA reported in this paper may be improved and/or extended. For example, since the proposed GA takes into account the entire network topology its scalability may be poor in large-scale networks. Therefore, it is necessary to develop distributed/decentralized versions of the proposed GA. This can be done partially by subdividing network coding into the problem of choosing an appropriate coding subgraph (flow-based or queue length based approaches) and characterizing the throughput of network coding along with random and deterministic code constructions.

Furthermore, the DNCP is a major concern of this study but there are still many important issues in dynamic environments to be addressed. For instance, the proposed GA exhibits robustness to some extent against certain changes in network topology but more theoretical work needs to be done to reveal such robustness in more depth, and effective methods/guidelines should be developed to improve such robustness in the future.

The simulation results show that the field size might not be so important in the case of exact network coding as it is to random network coding. However, further effort is needed in order to explore this issue more thoroughly. In specific terms, it could be very useful to develop some results which can achieve the target rate by minimizing the field size together with coding resources. Although the networks adopted in the simulation were widely used as benchmark problems in previous studies, they are relatively simple and thus a crucial next step is to test the proposed GA, probably in a modified form, on some real-world large-scale networks, such as wireless sensor networks.

دانلود ترجمه تخصصی این مقاله دانلود رایگان فایل pdf انگلیسی