One-to-one embedding between honeycomb mesh and Petersen-Torus networks

Area of Science:

• Computer Science
• Network Engineering
• Parallel Processing

Background:

• Wireless Sensor Networks (WSNs) often utilize honeycomb mesh structures for parallel processing.
• Developing new parallel algorithms for novel interconnection networks incurs significant research costs.
• Reusability of existing algorithms is crucial for efficient network design and deployment.

Purpose of the Study:

• To investigate the embedding of the honeycomb mesh (HMn) algorithm within the Petersen-Torus (PT(n,n)) interconnection network.
• To enable the reuse of established honeycomb mesh algorithms in the newer Petersen-Torus architecture.
• To minimize processor throughput degradation when running honeycomb mesh algorithms on the Petersen-Torus.

Main Methods:

• Proposing a novel one-to-one embedding algorithm for HMn into PT(n,n).
• Analyzing the performance metrics of the proposed embedding: dilation, congestion, and expansion.
• Mathematical proof and analysis of the embedding's topological properties.

Main Results:

• The proposed one-to-one embedding algorithm achieves a dilation of 5.
• The algorithm demonstrates a congestion factor of 2.
• An expansion ratio of 5/3 is calculated for the embedding.

Conclusions:

• The developed embedding algorithm effectively maps honeycomb mesh structures onto the Petersen-Torus.
• The achieved dilation and congestion values are suitable for practical WSN applications.
• This research facilitates the efficient utilization of parallel algorithms across different network architectures, reducing development costs.