# Distance-Only Task Orchestration Algorithm for Energy Efficiency in
Satellite-Based Mist Computing

Messaoud Babaghayou 1, Noureddine Chaib 1, Leandros Maglaras 2,
Yagmur Yigit 2, and Mohamed Amine Ferrag 3  1 LIM Laboratory. Laghouat
University, Laghouat, Algeria
2 School of Computing, Engineering and The Build Environment, Edinburgh Napier
University, United Kingdom
3 Technology Innovation Institute (TII), Abu Dhabi, United Arab Emirates
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper addresses the challenge of efficiently offloading heavy computing
tasks from ground mobile devices to the satellite-based mist computing
environment. With ground-based edge and cloud servers often being
inaccessible, the exploitation of satellite mist computing becomes imperative.
Existing offloading algorithms have shown limitations in adapting to the
unique characteristics of heavy computing tasks. Thus, we propose a heavy
computing task offloading algorithm that prioritizes satellite proximity. This
approach not only reduces energy consumption during telecommunications but
also ensures tasks are executed within the specified timing constraints, which
are typically non-time-critical. Our proposed algorithm outperforms other
offloading schemes in terms of satellites energy consumption, average end-to-
end delay, and tasks success rates. Although it exhibits a higher average VM
CPU usage, this increase does not pose critical challenges. This distance-
based approach offers a promising solution to enhance energy efficiency in
satellite-based mist computing, making it well-suited for heavy computing
tasks demands.

###### Index Terms:

satellite-based mist computing, energy efficiency, task orchestration, heavy
computing offloading, proximity-based offloading algorithm

##  I Introduction

In recent years, we have witnessed a profound transformation in the landscape
of mobile computing, catalyzed by the convergence of two compelling visions:
the Internet of Things (IoT) and the advent of 5G communications. This
paradigm shift has steered mobile computing away from the traditional
centralized Mobile Cloud Computing model towards the realms of Mobile Edge
Computing (MEC) [1, 2]. From another corner, over four decades ago, the
pioneers of satellite communication, J. R. Pierce and R. Kompfner, embarked on
a visionary exploration of transoceanic communication possibilities through
satellite technology. Their seminal work delved into myriad considerations,
encompassing alternative satellite repeater concepts, intricate discussions on
orbital dynamics, the optimization of satellite constellations, the
intricacies of path-loss calculations, the evolution of modulation systems,
and the persistent unknowns in satellite communications. It is remarkable that
despite the passage of almost 40 years, the core principles they laid down
have been the foundation for the field [3].

The ascent of IoT and satellite-to-satellite communication has become an
undeniable reality, charting a promising trajectory for the satellite market.
Presenting a transformative narrative, a comprehensive report from global
industry analysts underscores the significance of satellite-to-satellite IoT
services. This paradigm shift is fueled by the ever-expanding needs of global
enterprises and governments, who seek to monitor, manage, and assert control
over geographically dispersed assets, both stationary and mobile. The
satellite-to-satellite IoT services market is poised for substantial growth.
Evidently, satellite operators are actively responding to this burgeoning
demand by offering comprehensive IoT solution packages, harnessing the
capabilities of satellite technology [4]. As a consequence, edge computing
within the satellite domain has garnered increasing attention from various
stakeholders. This approach comprises distinct layers, as shown in Fig. 1,
including the mist or edge devices layer, followed by the data centers layer,
culminating in the cloud layer, each representing progressively higher
altitudes.

Figure 1: The general satellite edge computing architecture.

Within this transformative landscape of mobile and satellite communications,
the demand for ”heavy computing tasks” emerges as a crucial consideration.
These tasks encompass a spectrum of compute-intensive operations, ranging from
intricate calculations involved in satellite communication optimizations to
the demanding processing needs of blockchain-based IoT frameworks. In UAVs,
these tasks involve video preprocessing, pattern recognition, and feature
extraction, requiring substantial computational capabilities [5]. On the other
hand, in blockchain integration within IoT, heavy computing arises during the
mining process, demanding significant processing power [6]. The authors’
research delves into the efficient handling of such computationally intensive
tasks within the satellite-based mist computing environment, aiming to
optimize energy consumption and ensure timely task execution. This novel
approach represents a pivotal step towards accommodating heavy computing tasks
and fostering a more efficient satellite-based mist computing paradigm.

It is imperative to emphasize that the meticulous preservation of privacy and
security is paramount in IT systems in general [7, 8], and in the realm of
satellite-based mist computing in particular [9]. These critical aspects serve
as the bedrock upon which the success and reliability of the entire system
stand. Failing to uphold robust privacy and security measures would render the
system vulnerable to breaches by adversaries and malicious actors, potentially
leading to severe consequences that can undermine the efficacy and
trustworthiness of the entire infrastructure. Therefore, a vigilant and
proactive approach to safeguarding privacy and security is essential to
fortify the foundations of satellite-based mist computing and ensure its
continued success.

Furthermore, the meticulous preservation of Quality of Service (QoS),
encompassing crucial factors such as latency and various types of delays, is
vital. This applies not only to general IT systems [10] but also holds
particular significance within the context of satellite systems [4]. The
seamless operation and performance of these systems hinge upon the consistent
delivery of QoS standards, making it imperative to maintain and optimize these
aspects for their sustained effectiveness.

This paper contributes to the field of satellite-based mist computing with the
following key contributions:

  * •

Distance-Based Task Offloading Algorithm: We introduce a novel algorithm for
task orchestration that prioritizes proximity to satellites, allowing for
efficient and energy-conscious offloading of heavy computing tasks from ground
mobile devices. This approach is tailored to meet the timing requirements of
such tasks, which are often non-time-critical.

  * •

Enhanced Energy Efficiency: Our proposed algorithm significantly reduces
energy consumption during task execution by optimizing the use of nearby
satellites, making it an environmentally and economically sustainable
solution.

  * •

Improved Tasks Success Rate: Through proximity-based offloading, our algorithm
enhances the overall success rate of task execution, ensuring that heavy
computing tasks are reliably completed in a satellite-based environment.

  * •

Reduced End-to-End Delay: We demonstrate that the distance-based approach
leads to a substantial reduction in average end-to-end task execution delay,
which is critical for meeting performance expectations.

The remainder of this paper is organized as follows: In Section II, we review
related works in satellite communications technology, establishing the context
for our study. Section III introduces our system model, outlining key
components and parameters governing satellite edge computing. Section IV
delves into task deployment strategies, including common methods and our
distance-only approach, facilitating detailed comparisons. Section V presents
outcomes from extensive experimentation and simulations, analyzing performance
metrics such as latency, energy consumption, CPU utilisation and overall tasks
success rates. Finally, in Section VI, we summarise our findings and highlight
the significance of our proposed approach in optimizing heavy computing tasks
for satellite edge computing environments, paving the way for more efficient
satellite-based applications and giving future works and directions.

##  II Related Work

A recent study by Wang et al. [11] explores the potential of Low Earth Orbit
(LEO) satellites in satellite-based edge computing. LEO satellites offer wide
coverage and low latency, making them valuable for providing computing
services to user access terminals. The study focuses on resource allocation
challenges in Edge Computing Satellites (ECS) due to diverse resource
requirements and access planes. It proposes a three-layer network architecture
with a software-defined networking (SDN) model to manage inter-satellite links
(ISLs) and ECS resource scheduling. Advanced algorithms like the Advanced
K-means Algorithm (AKG) and a breadth-first-search-based spanning tree
algorithm (BFST) are employed for resource allocation and ISL construction.
Simulation results affirm the feasibility and effectiveness of this dynamic
resource scheduling scheme, addressing key challenges in satellite-based edge
computing systems.

Zhang et al. conducted a study to explore the vital integration of satellite
and terrestrial networks in the context of 6G wireless architectures [12].
These integrated networks are essential for delivering robust and secure
connectivity over expansive geographic areas. The authors introduce the
concept of double-edge intelligent integrated satellite and terrestrial
networks (DILIGENT), emphasizing the need for synergizing communication,
storage, and computation capabilities between satellite and cellular networks.
Leveraging multi-access edge computing (MEC) technology and artificial
intelligence (AI), the DILIGENT framework is designed for systematic learning
and adaptive network management. The article provides an overview of academic
research and standardization efforts, followed by an in-depth exploration of
the DILIGENT architecture, highlighting its advantages. Strategies such as
task offloading, content caching, and distribution are discussed, with
numerical results demonstrating the superior performance of this network
architecture compared to existing integrated networks.

The authors in [13] delve into the growing significance of the Internet of
Things (IoT) in the information industry. To address challenges related to
network distance and remote IoT device deployment, edge computing emerges as a
promising paradigm. In scenarios where IoT devices are situated in remote or
inaccessible areas, relying on satellite communication becomes imperative.
However, conventional satellites are often specialized and lack universal
computing capabilities. The proposed solution involves transforming
traditional satellites into space edge computing nodes, enabling dynamic
software loading, resource sharing, and coordinated services with the cloud.
The article outlines the hardware structure and software architecture of such
satellites and presents modelling and simulation results. Findings indicate
that the space edge computing system exhibits superior performance in terms of
reduced time and energy consumption compared to traditional satellite
constellations, with service quality influenced by satellite quantity,
performance, and task offloading strategies.

Gao et al. [14] focus on the role of satellite networks as complements to
terrestrial networks, catering to the computing needs of Internet of Things
(IoT) users in remote regions. Given the inherent limitations of satellites,
including constraints in computing power, storage, and energy, an innovative
approach involves breaking down IoT user computation tasks into segments and
leveraging multiple satellites for collaborative processing to enhance
satellite network efficiency. The integration of Network Function
Virtualization (NFV) technology with satellite edge computing is an emerging
area of interest. The paper introduces a potential game-based solution for
Virtual Network Function (VNF) placement within satellite edge computing. The
objective is to minimize deployment costs for individual user requests while
maximizing the provision of computing services across the satellite network.
This optimization problem is formulated as a potential game, aiming to
maximize overall network benefits through a game-theoretical approach. The
proposed decentralized resource allocation algorithm, based on a potential
game (PGRA), seeks a Nash equilibrium to effectively address the VNF placement
challenge. Experimental simulations validate the efficacy of the PGRA
algorithm in solving the VNF placement problem within satellite edge
computing.

In their study [2], introduce the OVR scheme, emphasizing its significance in
addressing location privacy and road congestion challenges within the Internet
of Vehicles (IoV). OVR innovatively leverages silent periods to enhance
location privacy and manage congestion in real time. Comparative evaluations
against existing privacy schemes highlight OVR’s superior performance in
privacy and QoS.

##  III System Model

In order to provide a comprehensive depiction of the system model employed, we
elucidate the fundamental components taken into account both during the
formulation of our approach and its subsequent evaluation. These components
are stated as follows:

  * •

Generated heavy computing tasks: They are the tasks that are being generated
from ground-level sources like IoT devices, UAVs [15] or mobile devices and
are typically processed at the satellite level. We assume that it starts from
the mist nodes level. Our work addresses the challenge of efficiently managing
these tasks by prioritizing proximity to satellites in task offloading. This
ensures that heavy computing tasks are processed efficiently while considering
their origin and timing requirements.

  * •

Mist nodes: they refer to the integral components of the satellite-based mist
computing infrastructure. These nodes serve as the intermediary layer,
responsible for executing heavy computing tasks offloaded from ground devices
or relaying them to cloud satellites or edge datacenters. They play a pivotal
role in optimizing the processing of tasks, reducing latency, and enhancing
the overall efficiency of the mist computing system.

  * •

Edge datacenters are essential components, serving as critical hubs for
processing data and heavy computing tasks. These datacenters play a key role
in our three-tier architecture, offering a balance between local processing
and centralized cloud resources. They help reduce latency, enhance
responsiveness, and facilitate efficient task execution in satellite-based
mist computing, ultimately contributing to improved system performance. They
also may run Artificial Intelligence (AI) techniques to achieve various
objectives [16]

  * •

Cloud computing centers are central facilities in the satellite-based mist
computing architecture. They provide the vast computational resources needed
to support heavy computing tasks and data processing. While they may not be as
geographically proximate as edge datacenters, they serve as essential
backbones for the system, ensuring scalability and reliability. These centers
are a crucial component in our three-tier architecture, contributing to the
overall efficiency and effectiveness of satellite-based mist computing.

##  IV Methodology

Our methodology is designed to address the unique challenges posed by heavy
computing task offloading in a satellite-based mist computing environment. We
emphasize the need to efficiently manage tasks originating from ground-level
sources, including IoT devices, UAVs, and other mobile devices. The primary
objective of our methodology is to optimize energy efficiency, reduce end-to-
end delay, and improve tasks success rates in this context.

###  IV-A Task Orchestration Algorithm Development

To achieve efficient task orchestration, we have proposed a novel distance-
based algorithm that takes into consideration the closest destination in which
the generated heavy computing tasks would be executed. This algorithm focuses
on the following two aspects:

####  IV-A1 Proximity-Based Offloading

Our algorithm prioritizes satellites that are geographically closer to the
source of the tasks. This ensures that task offloading is energy-efficient,
taking into account the practicality of processing tasks generated from
ground-level devices. We consider that the tasks are generated from the mist
nodes level for simplicity.

####  IV-A2 Timing Requirements

Recognizing that heavy computing tasks are often non-time-critical, we
designed the algorithm to handle them within their specified timing
constraints, which are large to some extent. Nevertheless, we tend towards
lower end-to-end delays for optimum results.

###  IV-B Experimental Evaluation

To assess the effectiveness of our methodology, we conducted a comprehensive
experimental evaluation. We compared our distance-based algorithm with
existing offloading schemes, considering the following key performance
metrics:

####  IV-B1 VM CPU Usage

We monitored the average VM CPU usage, ensuring it remained within acceptable
limits and did not introduce critical resource constraints.

####  IV-B2 Average End-to-End Delay

We analyzed the average time it takes for tasks to be successfully completed,
taking into account the specific timing requirements of heavy computing tasks
that are, in this case scenario, large.

####  IV-B3 Satellites Energy Consumption

We measured the energy consumption of satellites during task execution to
evaluate the energy efficiency of our approach.

####  IV-B4 Tasks Success Rate

We assessed the overall success rate of task execution to gauge the
reliability of our methodology since this metric is so critical and having a
lot of failing tasks would impact the effectiveness of the approach.

###  IV-C Task Orchestration Algorithms

To comprehensively assess the effectiveness of our proposed distance-based
algorithm, we have selected four additional task orchestration algorithms that
are implemented and used in the work done by Wei et al. in [17]. These chosen
algorithms serve as benchmarks and are essential for the comparative
evaluation alongside our proposed algorithm. They are stated as follows:

####  IV-C1 Distance_Only

Our Distance_Only Algorithm, at its core, is designed to optimize task
orchestration in a satellite-based mist computing environment. It accomplishes
this by prioritizing proximity as the primary factor in deciding where and how
to offload heavy computing tasks. By considering the physical distance between
the source satellite and potential offloading destinations, this algorithm
aims to minimize energy consumption, reduce end-to-end delays and ensure high
tasks success rates. This approach ensures that tasks are efficiently
processed, especially those originating from ground-level devices, such as IoT
sensors, UAVs and mobile devices where their available resources are so
restricted. Algorithm 1 explains the operational principles of our proposed
algorithm.

Data: architecture (list of available resources), task (the task to be
offloaded)

Result: Selected VM for Task Offloading

1

2Create an empty list ’distance’;

3 foreach  _VM in ’orchestrationHistory’_ do

4 Calculate the distance delay (’distance_tem’) for the VM and the task;

5 Add ’distance_tem’ to the ’distance’ list;

6

7Standardize the ’distance’ values and store them in ’distance_stand’;

8 Initialize ’vm’ to -1 and ’min’ to -1;

9 foreach  _VM in ’orchestrationHistory’_ do

10 if  _offloading the task to the current VM is possible_ then

11 Calculate ’min_factor’ based on the standardized delay from
’distance_stand’;

12 if  _’min’ is -1_ then

13 Set ’min’ to ’min_factor’ and ’vm’ to the current VM;

14

15 else if  _’min_factor’ is less than ’min’_ then

16 Update ’min’ to ’min_factor’ and ’vm’ to the current VM;

17

18

19

20Return the selected VM (’vm’) for task offloading;

Algorithm 1 Distance_Only Algorithm

####  IV-C2 Round_Robin

it operates by choosing the satellite node with the fewest assigned tasks,
thus promoting a balanced distribution of the computing workload. By
prioritizing underutilized resources, it aims to prevent resource bottlenecks
and alleviate the strain on heavily loaded nodes. This equitable distribution
strategy contributes to optimal system performance and task completion rates.
Furthermore, it minimizes the likelihood of overburdening any single satellite
node, ensuring that all resources are used efficiently and effectively. In
scenarios where task requirements vary, the scheme serves as a fair and
pragmatic approach for optimizing task deployment in satellite-based mist
computing environments.

####  IV-C3 Trade_Off

it follows a dynamic approach that intelligently selects the most suitable
satellite node based on a nuanced balance of factors, including latency,
energy consumption, and resource availability. This algorithm evaluates each
candidate satellite node, considering the node’s type (cloud or edge device),
the number of waiting tasks, available CPU processing power, and specific task
characteristics. By calculating a combined weighted score for each candidate,
this scheme ensures tasks are allocated to the satellite, offering the most
optimal trade-off between these factors. This approach enhances the efficiency
and effectiveness of task orchestration, optimizing satellite resource
utilization in satellite-based mist computing environments.

####  IV-C4 Random_VM

itintroduces an element of randomness into the selection of the most suitable
satellite node for task deployment. It compiles a list of available VMs and
utilizes a randomization strategy to assign tasks, promoting load balancing
and diversification among satellite nodes. The process randomly selects a VM
index and verifies its suitability for task offloading. This approach adds an
element of unpredictability to task assignment, reducing the risk of
overloading specific nodes. If a suitable VM is not found through random
selection, the scheme systematically scans for an eligible VM, ensuring
equitable resource utilization and offering a dynamic approach to task
deployment in satellite-based mist computing environments.

####  IV-C5 WEIGHT_GREEDY (WG)

it is a sophisticated approach designed for satellite-based mist computing
environments. It incorporates a comprehensive evaluation of four critical
performance indicators: transmission distance, CPU processing time, number of
parallel tasks, and equipment energy consumption. What sets ”WEIGHT_GREEDY” as
a good scheme is its fine-tuned weighting of these indicators, where the
ratios are adjusted by its authors to be 6:6:5:3. This means that factors
related to task timeliness and minimal energy consumption are prioritized due
to their significant weight. In a satellite edge computing scenario, where
timely task execution and energy efficiency are paramount, this weighting
ratio ensures that the scheme optimally balances the competing demands of low
latency and minimal power consumption.

##  V Results and Discussion

###  V-A Simulation Environment

In our simulations, we leveraged the ”SatEdgeSim” simulator [17], an
innovative toolkit tailored for modeling and simulating performance evaluation
in satellite edge computing environments. ”SatEdgeSim” is built upon the
foundation of the well-established ”PureEdgeSim” simulator [18], which, in
turn, relies on the widely recognized ”CloudSim Plus” cloud computing
simulator [19]. This strategic choice streamlines the development process, as
it eliminates the need to construct the underlying code for traditional cloud
computing and fog, edge or mist computing environments. Instead, ”SatEdgeSim”
can focus its efforts on creating a specialized satellite edge computing
environment that aligns with the functional and performance requirements of
this unique domain. This framework enables researchers to conduct
comprehensive simulations and evaluate task deployment strategies within a
satellite-based mist computing context.

###  V-B Experimental Setup

A comprehensive overview of the experimental setup is encapsulated within
Table I for a convenient reference.

TABLE I: Experimental Setup Parameters Parameter |  Value
---|---
Simulation Time |  10 minutes
Updating Interval |  1 second
Satellite Minimum Height |  400,000 meters
Maximum Mist Satellites Communication Range |  32,000,000 meters
Maximum Edge Datacenter Satellites Communication Range |  36,000,000 meters
Maximum Cloud Satellites Communication Range |  40,000,000 meters
Number of Mist Satellites |  1000
Number of Edge Datacenter Satellites |  24
Number of Cloud Satellites |  18
Progression by Each Iteration |  100 satellites
Tasks Generation Rate |  20 tasks per minute
Type of Tasks |  Heavy Computing Tasks
WLAN Bandwidth |  1000 megabits per second
WAN Propagation Speed |  300,000,000 meters per second
Coordinate Positions |  Determined using the STK tool (Satellite Tool Kit)
Consumed Energy |  0.00000005 J per bit
Amplifier Dissipation Free Space |  0.00000000001 J per bit per m2
Amplifier Dissipation Multipath |  0.0000000000000013 J per bit per m4
Orchestration Architectures |  Utilize all layers (Mist, Edge Datacenters, Cloud)
Orchestration Algorithms |  Round_Robin, Trade_Off, Random_VM, WG, Distance_Only

###  V-C Simulation Results

In this section, we present the results of our extensive evaluation and
comparative analysis of five task orchestration algorithms. Specifically, we
examined the performance of Round_Robin, Trade_Off Random_VM, WG and our
proposed Distance_Only algorithm. These algorithms were rigorously assessed
using a set of critical metrics, including VM CPU Usage, Average End-to-End
Delay, Satellites Energy Consumption, and Tasks Success Rate. Our findings
shed light on the effectiveness and efficiency of these task orchestration
strategies in the context of satellite-based mist computing environments.

####  V-C1 VM CPU Usage

The examination of VM CPU Usage across varying numbers of satellites, as shown
in Fig. 2, revealed distinctive patterns among the task orchestration
algorithms. Notably, Round_Robin, Trade_Off and Random_VM exhibited
consistently low CPU utilization, which proportionally increased with the
satellite count. In contrast, the WG algorithm consumed a higher CPU
utilization, ranging from 0.7 percent to 5.1 percent as the satellite numbers
increased. Our proposed Distance_Only algorithm displayed CPU utilization that
initiated at approximately 4.8 percent and gradually rose to 7.1 percent with
the expansion of satellite nodes.

Figure 2: VM CPU Usage of the orchestration algorithms

####  V-C2 Average End-to-End Delay

A thorough examination of Average End-to-End Delay across the spectrum of task
orchestration algorithms, as shown in Fig. 3, revealed a common trend: an
increase in end-to-end delay as the number of satellites expanded. Notably,
our proposed Distance_Only algorithm emerged as the frontrunner in this
aspect, showcasing the best performance with an end-to-end delay variation
ranging from 2.5 seconds to 5.5 seconds. In contrast, among the remaining
algorithms, Trade_Off exhibited the most challenging performance, with an end-
to-end delay fluctuating between 4.5 seconds and 9.1 seconds.

Figure 3: Average End-to-End Delay of the orchestration algorithms

####  V-C3 Satellites Energy Consumption

The evaluation of energy consumption among the task orchestration algorithms
that is shown in Fig. 4 unveiled notable distinctions in performance. Our
Distance_Only scheme exhibited exceptional energy efficiency, maintaining a
consistently low energy consumption ranging from 165 dBW to 174 dBW. This
energy consumption exhibited minimal variation even as the number of
satellites increased. In contrast, Round_Robin, Trade_Off and Random_VM
showcased notably higher energy consumption, with a marginal increase as the
satellite count grew, resulting in values fluctuating between 218 dBW and
approximately 237 dBW. The WG algorithm fell between these extremes, consuming
energy in the range of 212 dBW to 218 dBW

Figure 4: Satellites Energy Consumption of the orchestration algorithms

####  V-C4 Tasks Success Rate

The examination of Tasks Success Rate across varying numbers of satellites, as
shown in Fig. 5, highlighted intriguing trends among the task orchestration
algorithms. Notably, our proposed Distance_Only scheme showcased an impressive
performance, consistently maintaining a 100 percent success rate while the
satellite count increased up to 800 satellites. Beyond this point, a
noticeable decline was observed, settling at 93.8 percent with 1000
satellites. This pattern was mirrored in Round_Robin, Trade_Off, Random_VM and
WG, commencing at approximately 99.5 percent and descending to below 93
percent as the satellite count increased. Additionally, it’s worth noting that
the WG algorithm exhibited the least favorable performance among the five
schemes, characterized by a non-smooth variation between 100 and 1000
satellites.

Figure 5: Achieved tasks success rate of the orchestration algorithms

###  V-D Discussion

In this section, we provide interpretations of the results obtained from the
four metric evaluations, shedding light on the performance of the task
orchestration algorithms in a satellite-based mist computing environment.

For the VM CPU Usage, the relatively high CPU utilization observed in our
Distance_Only scheme can be attributed to its heavy reliance on mist-level
satellites, which represent the lowest level in the architecture. By
distributing heavy computing tasks among these satellites, the average CPU
consumption naturally rises, surpassing that of other schemes that leverage
resources from multiple satellite levels. While a high average CPU consumption
may not be the most desirable outcome, it remains at a manageable level, which
can be tolerated without causing critical issues.

In the Average End-to-End Delay, the Distance_Only scheme excelled in
achieving the best delay performance, owing to the inherent importance of
satellite communication distances. Leveraging communication between satellites
at the mist level ensures shorter delays, even when handling high-computing
tasks. This efficient communication structure contributes significantly to
minimizing end-to-end delays.

In the Satellites Energy Consumption, our scheme demonstrated commendable
performance in energy consumption, achieving approximately a 20 percent of
energy gain compared to other schemes. This can be attributed to the short
distances between mist-level satellites, which are in close proximity to each
other. This close proximity results in reduced energy consumption during
satellite-to-satellite communication, contributing to more efficient energy
usage.

Finally, in the Tasks Success Rate, our proposed Distance_Only scheme
exhibited exceptional performance by consistently maintaining a very high
success rate, reaching 100 percent during the initial stages, in contrast to
the other schemes. The significant difference can be attributed to the
scheme’s reliance on closely situated mist-level satellites, which minimizes
task failures due to mobility, a common cause of task failure. However, the
remarkable decrease observed as the number of satellites increased is due to
execution delays of heavy computing tasks, which may not always be met,
particularly with a higher number of satellites. This can lead to some mist
satellites experiencing overloaded queues, resulting in delays that breach the
task constraints.

At last, our Distance_Only task orchestration scheme showcased a balanced
performance, excelling in terms of end-to-end delay, energy consumption, and
task success rates. While it exhibited higher CPU utilization, it remained
within acceptable limits. These findings emphasize the efficacy of our
proposed scheme in optimizing resource utilization and performance metrics in
satellite-based mist computing environments.

##  VI Conclusion and Future Work

In conclusion, the results of our comprehensive evaluation of task
orchestration algorithms in a satellite-based mist computing environment
underscore the significance of selecting the right approach to optimize
resource utilization and performance. Our proposed Distance_Only scheme,
despite exhibiting higher CPU utilization, excelled in terms of end-to-end
delay, energy consumption, and task success rates. These findings emphasize
its efficacy in managing task orchestration efficiently.

As we look to the future, several directions for further research and
development become apparent. One key area of exploration involves the
development of adaptive variants of our Distance_Only scheme. These adaptive
approaches could account for the challenges arising from an increasing number
of satellites, particularly addressing queue congestion and management issues.
By dynamically adapting to the changes of loads, such variants can further
enhance task orchestration performance.

Additionally, future research may delve into the utilization of cross-level
satellites task offloading. This innovative approach would enable satellites,
that use the Distance_Only scheme, to intelligently balance their offloading
by harnessing resources from other levels, including edge datacenters and
cloud-level resources. By creating a dynamic, multi-tiered orchestration
framework, we can optimize task allocation and resource utilization across the
entire satellite-based ecosystem.

In the evolving landscape of satellite-based mist computing, our findings and
future directions highlight the importance of continued research and
innovation in task orchestration algorithms to meet the growing demands of
modern satellite networks and ensure their seamless operation in a multitude
of applications.

## References

  * [1] Yuyi Mao, Changsheng You, Jun Zhang, Kaibin Huang, and Khaled B Letaief.  A survey on mobile edge computing: The communication perspective.  IEEE communications surveys & tutorials, 19(4):2322–2358, 2017.
  * [2] Messaoud Babaghayou, Noureddine Chaib, Nasreddine Lagraa, Mohamed Amine Ferrag, and Leandros Maglaras.  A safety-aware location privacy-preserving iov scheme with road congestion-estimation in mobile edge computing.  Sensors, 23(1):531, 2023.
  * [3] William W Wu.  Satellite communications.  Proceedings of the IEEE, 85(6):998–1010, 1997.
  * [4] Mauro De Sanctis, Ernestina Cianca, Giuseppe Araniti, Igor Bisio, and Ramjee Prasad.  Satellite communications supporting internet of remote things.  IEEE Internet of Things Journal, 3(1):113–123, 2015.
  * [5] Mohamed-Ayoub Messous, Sidi-Mohammed Senouci, Hichem Sedjelmaci, and Soumaya Cherkaoui.  A game theory based efficient computation offloading in an uav network.  IEEE Transactions on Vehicular Technology, 68(5):4964–4974, 2019.
  * [6] Yong Yan, Yao Dai, Zhiqiang Zhou, Wei Jiang, and Shaoyong Guo.  Edge computing-based tasks offloading and block caching for mobile blockchain.  Comput. Mater. Contin, 62(2):905–915, 2020.
  * [7] Messaoud Babaghayou, Nabila Labraoui, Mohamed Amine Ferrag, and Leandros Maglaras.  Between location protection and overthrowing: a contrariness framework study for smart vehicles.  In 2021 IEEE International Conference on Consumer Electronics (ICCE), pages 1–5. IEEE, 2021.
  * [8] Messaoud Babaghayou, Nabila Labraoui, Ado Adamou Abba Ari, Mohamed Amine Ferrag, and Leandros Maglaras.  The impact of the adversary’s eavesdropping stations on the location privacy level in internet of vehicles.  In 2020 5th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM), pages 1–6. IEEE, 2020.
  * [9] Georg Baselt, Martin Strohmeier, James Pavur, Vincent Lenders, and Ivan Martinovic.  Security and privacy issues of satellite communication in the avlatlon domain.  In 2022 14th International Conference on Cyber Conflict: Keep Moving!(CyCon), volume 700, pages 285–307. IEEE, 2022.
  * [10] Mehmet Dagli, Selcuk Keskin, Yagmur Yigit, and Adem Kose.  Resiliency analysis of onos and opendaylight sdn controllers against switch and link failures.  In 2020 Fifth International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN), pages 149–153. IEEE, 2020.
  * [11] Feng Wang, Dingde Jiang, Sheng Qi, Chen Qiao, and Lei Shi.  A dynamic resource scheduling scheme in edge computing satellite networks.  Mobile Networks and Applications, 26:597–608, 2021.
  * [12] Jiaxin Zhang, Xing Zhang, Peng Wang, Liangjingrong Liu, and Yuanjun Wang.  Double-edge intelligent integrated satellite terrestrial networks.  China Communications, 17(9):128–146, 2020.
  * [13] Yuxuan Wang, Jun Yang, Xiye Guo, and Zhi Qu.  Satellite edge computing for the internet of things in aerospace.  Sensors, 19(20):4375, 2019.
  * [14] Xiangqiang Gao, Rongke Liu, and Aryan Kaushik.  Virtual network function placement in satellite edge computing with a potential game approach.  IEEE Transactions on Network and Service Management, 19(2):1243–1259, 2022.
  * [15] Yagmur Yigit, Long D Nguyen, Mehmet Ozdem, Omer Kemal Kinaci, Trang Hoang, Berk Canberk, and Trung Q Duong.  Twinport: 5g drone-assisted data collection with digital twin for smart seaports.  Scientific Reports, 13(1):12310, 2023.
  * [16] Messaoud Babaghayou, Noureddine Chaib, Mohamed Amine Ferrag, and Leandros Maglaras.  An ai-assisted model for task offloading decision making in edge computing.  In Colloque sur les Objets et Systèmes Connectés 2023, 2023.
  * [17] Junyong Wei, Suzhi Cao, Siyan Pan, Jiarong Han, Lei Yan, and Lei Zhang.  Satedgesim: A toolkit for modeling and simulation of performance evaluation in satellite edge computing environments.  In 2020 12th International Conference on Communication Software and Networks (ICCSN), pages 307–313. IEEE, 2020.
  * [18] Charafeddine Mechalikh, Hajer Taktak, and Faouzi Moussa.  Pureedgesim: A simulation framework for performance evaluation of cloud, edge and mist computing environments.  Computer Science and Information Systems, 18(1):43–66, 2021.
  * [19] Manoel C Silva Filho, Raysa L Oliveira, Claudio C Monteiro, Pedro RM Inácio, and Mário M Freire.  Cloudsim plus: a cloud computing simulation framework pursuing software engineering principles for improved modularity, extensibility and correctness.  In 2017 IFIP/IEEE symposium on integrated network and service management (IM), pages 400–406. IEEE, 2017.


# Root clusters of irreducible polynomials

M Krithika and P Vanchinathan

###### Abstract

For a field $F$, and a fixed algebraic closure $\bar{F}$, two roots
$\alpha,\beta$ of an irreducible polynomial over $F$ are said to be in the
same root cluster if $F(\alpha)=F(\beta)$ (not merely isomorphic). Clusters
provide a partition of the set of roots, and all clusters are of the same
size, a divisor of the degree of $f(x)$. This was proved by Perlis [1], For
$F=\mathbf{Q}$, a positive integer $n\geq 3$ and any $d$ we show how to
construct irreducible polynomials $g(x)$ of degree $nd$ and cluster size $d$.

Division of Mathematics

VIT University

Vandalur–Kelambakkam Road

Chennai, 600 127 INDIA

Keywords: Roots of polynomials; root cluster; Galois theory

AMS Classification: 11R32, 12F05

##  1 Introduction

In Galois theory the splitting field of an irreducible polynomial $f(x)$,
i.e., the field obtained by adjoining all the roots of $f(x)$, is the main
object of study. The very definition of this implicitly admits the reality
that, with just a single root, the field generated may be much smaller than
the splitting field. For an irreducible polynomial with just one real root,
such as $x^{3}-2\in\mathbf{Q}[x]$, the field field generated by it will
contain no other roots.

So a natural question is: for a general irreducible polynomial how many of the
roots are found in the field generated by a single root ? Perlis in his paper
[1] published in 2003 remarks that most people seem to be unaware of this
problem. He provides answers to this question and also shows other
interpretations for this number. The delightful results in that short paper
seem to be not so well known.

######  Definition 1.

For an irreducible polynomial $f(x)$ over some field perfect field $F$, and a
root $\alpha$ of $f(x)$ in a fixed algebraic closure $\bar{F}$, by the root
cluster of $\alpha$ we mean the set of roots of $f(x)$ in the field
$F(\alpha)$. The cardinality of this set is called the root cluster size of
$\alpha$.

For simplicity sometimes we say cluster size to mean root cluster size.

Example 1 For any primitive element of a Galois extension $K/F$, all the roots
form a single cluster. So the root cluster size is the degree
$[K\mathrel{\mathop{\mathchar 58\relax}}F]$. We will tacitly omit this extreme
case in future.

Example 2 For integers $t\geq 7$, we can check $x^{4}-tx^{3}-x^{2}+tx+1$ has
$D_{4}$ as Galois group, and for any root $\alpha$, easy to see $-1/\alpha$ is
also a root, and so the root cluster number is 2.

What are the possible values of the cluster size for a general polynomial?
Perlis has answered this completely for $F=\mathbf{Q}$. For $n>2$, and a
divisor $r$, he shows the existence of an irreducible polynomial having root
clusters of cardinality $r$. His proof invokes a result of Shafarevich on the
existence of Galois extensions of $\mathbf{Q}$ for any given finite solvable
group.

Actually Perlis has shown many nice properties of this concept of root
clusters, and he proves that cluster size (which he calls as root quantum
number) is the same for all the roots of an irreducible polynomial. And so we
can, and do, talk of cluster size of an irreducible polynomial.

In this paper we provide a constructive procedure that starts from a
polynomial of lower cluster size and yields a higher degree polynomial with
proportionately higher cluster size. More precisely we prove:

######  Theorem 1.

Let $f(x)\in\mathbf{Q}[x]$ be the minimal polynomial of an algebraic number
$\alpha$ of degree $n>2$ with cluster size $r$ and let $K_{f}$ be its
splitting field. Assume there is an integer $m>1$ such that
$K_{f}\cap\mathbf{Q}(\zeta_{m})=\mathbf{Q}$. Then for each divisor $d$ of
$\phi(m)$ there exists a polynomial $g(x)$ of degree $nd$ with cluster size
$rd$. (Here $\phi$ denotes the Euler’s phi function).

Applying the above we were able to arrive at the following:

######  Theorem 2.

(a) For integers $n\geq 3,d\geq 1$ there exist an irreducible polynomial
$f(x)$ of degree $nd$ with root clusters of size $d$.

(b) For $n=2$, and $d$ any even number, there exist irreducible polynomials of
degree $2d$ with root cluster size $d$.

We would like to reiterate that whereas Theorem 1 above is novel, Theorem 2
has been already proved by Perlis and our work in this aspect provides an
alternative—arguably easier—construction of such polynomials.

We make no use of advanced results from Inverse Galois Theory. Only
requirements are existence of Galois extensions with $A_{n}$ as Galois groups,
and a technical result on linear disjointness that can be found in the book by
Jacobson.

This paper is organized as below. Section 2 lists the preliminaries, and also
lists major results of Perlis, and in Section 3 we provide a proof of Theorem
1 and in Section 3, Theorem 2 is proved as an application.

Acknowledgement: We would like to thank B.Sury for making us aware of the work
of Perlis.

##  2 Preliminaries

Even though this paper is exclusively devoted to polynomials over the field of
rational numbers, first we would like to summarise the results of Perlis that
need to be widely known (and will also be used in some of our proofs). They
are valid in general. For that purpose we set up the notation: For a general
perfect field, $K$ we consider $f(x)\in K[x]$ an irreducible polynomial of
degree $n$; $\alpha$ a root of $f$; $K_{f}$ the splitting field;
$G=\mathrm{Gal}\,(K_{f}/K)$; $H\subset G$ subgroup with $K(\alpha)$ as the
fixed field.

Now define numbers, $r_{K}(f)$ as the number of roots of $f$ lying in
$K(\alpha)$, and $s_{K}(f)$ as the number of distinct fields
$K(\alpha^{\prime})$, with $\alpha^{\prime}$ varying over all the $n$ roots of
$f(x)$.

Under this notation the results of Perlis can be stated:

######  Theorem 3.

(Perlis[1])

  * (i)

$r_{K}(f)$ is independent of the choice of the root $\alpha$ of $f(x)$.

  * (ii)

$r_{K}(f)$ divides the degree of $f(x)$.

  * (iii)

In fact $r_{K}(f)\cdot s_{K}(f)=\deg f$

  * (iv)

$r_{K}(f)$ is the index of the subgroup $H$ in its normaliser $N_{G}(H)$.

Hereafterwards we will be working over the field of rational numbers. We
recall now the results that we will be using later on.

######  Proposition 1.

For $n\geq 4$, any subgroup $H$ of $A_{n}$ with index $n$ is isomorphic to
$A_{n-1}$ and is a maximal subgroup.

The next result assures us that linear disjointness can be verified in stages.

######  Lemma 1.

[3, Lemma 1, Chapter 8.15]Let $E$ be an extension of $F$. Let $E_{1}$ and
$E_{2}$ be two extenions of $F$ contained in $E$, and $K_{1}$ an extension of
$F$ contained in $E_{1}$. Then $E_{1}$ and $E_{2}$ are linearly disjoint over
$F$ if and only if the following two conditions hold:

  * •

$K_{1}$ and $E_{2}$ are linearly disjoint over $F$ and

  * •

$K_{1}E_{2}$ and $E_{1}$ are linearly disjoint over $K_{1}$.

$F$$K_{1}$$E_{1}$$E_{2}$$K_{1}E_{2}$$E_{1}E_{2}$

##  3 Main Theorem

Now we present our proof of the main results. First we prove Theorem 1.

###### Proof.

Let the $n$ roots of $f(x)$ be
$\alpha=\alpha_{1},\alpha_{2},\ldots,\alpha_{n}$. Without loss of generality
assume the cluster of $\alpha$ is the first $r$ of these roots:
$\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{r}\\}$. As $K_{f}$ and
$\mathbf{Q}(\zeta_{m})$ are linearly disjoint the same is true for
$\mathbf{Q}(\alpha)$ and $\mathbf{Q}(\beta)$ for any subfield
$\mathbf{Q}(\beta)\subset\mathbf{Q}(\zeta_{m})$. Consequently $\alpha\beta$
has degree $nd$, with $d$ being the degree of $\beta$.

Let the conjugates of $\beta$ be $\beta=\beta_{1},\beta_{2},\ldots,\beta_{d}$.
They lie in $\mathbf{Q}(\beta)$ (because it is a Galois extension of
$\mathbf{Q}$).

We claim that the minimal polynomial $g(x)$ of $\alpha\beta$ which has degree
$nd$, has cluster size $rd$.

The conjugates of $\alpha\beta$ in $\mathbf{C}$ are $\alpha_{i}\beta_{j}$ for
$i=1,2,\ldots,n$ and $j=1,2,\ldots,d$. As $\alpha_{i}$ for $1\leq i\leq r$ are
in $\mathbf{Q}(\alpha)$, we can see that $\alpha_{i}\beta_{j}$ belong to
$\mathbf{Q}(\alpha\beta)$ for $i=1,2,\ldots,r$ and $j=1,2,\ldots,d$. So we
get:

  * (Cl)

The cluster of $\alpha\beta$ has at least $rd$ roots out of a total of $nd$
roots of $g(x)$.

Now we want to show no more roots besides what is in assertion (Cl) are in
$\mathbf{Q}(\alpha\beta)$. For that we layout the fields with the compositum
of $K_{f}$ and $\mathbf{Q}(\beta)$ at the top.

With our choice of $m$ ensuring linear disjointness of $\mathbf{Q}(\beta)$ and
$K_{f}$ over $\mathbf{Q}$, we can deduce, using Lemma 1, (see the diagram)

  * (P1)

$\mathbf{Q}(\alpha)$ and $\mathbf{Q}(\beta)$ are linearly disjoint over
$\mathbf{Q}$ and

  * (P2)

$K_{f}$ and $\mathbf{Q}(\alpha\beta)$ are also linearly disjoint over
$\mathbf{Q}(\alpha)$.

$\mathbf{Q}$$\mathbf{Q}(\alpha)$$K_{f}$$\mathbf{Q}(\beta)$$\mathbf{Q}(\zeta_{m})$$\mathbf{Q}(\alpha\beta)$$K_{f}\mathbf{Q}(\beta)$

Suppose now, to the contrary, the cluster of $\alpha\beta$ has more roots
besides the one shown in (Cl). Without loss of generality, say,
$\alpha_{r+1}\beta_{j}\in\mathbf{Q}(\alpha\beta)$ for some $j$. As
$\beta_{j}\in\mathbf{Q}(\beta)\subset\mathbf{Q}(\alpha\beta)$, we get
$\alpha_{r+1}\in\mathbf{Q}(\alpha\beta)$. Being the splitting field for
$f(x)$, we see that $\alpha_{r+1}\in K_{f}$. Which implies
$\alpha_{r+1}\in\mathbf{Q}(\alpha\beta)\cap K_{f}$. The linear disjointness in
statement (P2) above implies $\alpha_{r+1}\in\mathbf{Q}(\alpha)$.

This is a contradiction to the fact that the root cluster of $\alpha$ is
$\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{r}\\}$, Thus the cluster size of
$g(x)$ is $rd$.

∎

##  4 Applications

First let us establish a preliminary result which must be known to experts in
some other guise.

######  Proposition 2.

For all integers $n\geq 3$ there exist irreducible polynomials
$f(x)\in\mathbf{Q}[x]$ for which all root clusters are singletons.

###### Proof.

Case $n=3$: For any cubic irreducible polynomial with non-real roots, e.g.,
$x^{3}-2$, the clusters are all singletons as its unique real root can not
generate the other roots.

Case $n\geq 4$: There exist irreducible polynomials $f(x)$ of degree $n$ such
that their splitting fields $K_{f}$ has Galois group $A_{n}$ (see [4] which
states Laguerre polynomials have this property).

Let $\alpha$ be one of the roots of $f(x)$. Then $K=\mathbf{Q}(\alpha)$ is the
fixed field of some subgroup $H\subset A_{n}$ of index $n$.

By Proposition 1, $H$ is a proper maximal subgroup of the simple group
$A_{n}$, and hence $N_{G}(H)=H$. Then by part (iv) of Theorem 3 we can
conclude that the clusters are singletons. ∎

Now we give the proof of Theorem 2. Our main result starts with a seed
polynomial with a specific proportion of roots in a cluster and yields a
higher degree polynomial with the same proportion of roots in its clusters.

So to apply it, we need an appropriate seed polynomial.

First assume $n\geq 5$, let $f(x)$ be the irreducible polynomial of degree $n$
with Galois group $A_{n}$ as obtained in Proposition 2. This will be the seed.
We also requires the splitting field $K_{f}$ be linearly disjoint with
cyclotomic fields. This can be verified as below: As $A_{n}$ is simple, any
extension with Galois group $A_{n}$ does not admit intermediate extensions
which are Galois; whereas in cyclotomic extensions $\mathbf{Q}(\zeta_{m}$) for
any $m\geq 3$ all subfields are Galois, so their intersection can only be
$\mathbf{Q}$.

Now for any integer $d\geq 2$ by Dirichlet’s theorem choose a prime number $p$
with $d$ dividing $p-1$. Then for $m=p$ we have a subextension
$\mathbf{Q}(\beta)\subset\mathbf{Q}(\zeta_{p})$ of degree $d$ over
$\mathbf{Q}$. Now the minimal polynomial of $\alpha\beta$ where $\alpha$ is a
root of $f(x)$ will have cluster size $d$.

When $n=4$ we can start with an irreducible $f(x)$ whose splitting field
$K_{f}$ has Galois group $A_{4}$, and when $n=3$ we can choose the see $f$ to
be any irreducible cubic with only one real root. However in both the cases,
as the Galois group of $K_{f}$ is not simple, $K_{f}$ can possibly intersect a
cyclotomic field in a number field of degree${}>1$. This can be circumvented
as below.

After this $f(x)$ is chosen, we pick $p$ to be any prime bigger than those
ramifying in $K_{f}$ (appealing to the infiniteness part in Dirichlet’s
theorem on arithmetic progressions). As $p$ is the only prime ramifying in the
$p$-th cyclotomic extension its intersection with $K_{f}$ is guaranteed to be
extactly $\mathbf{Q}$.

Proof of part (b) with $n=2$ and $d$ even. For this case the seed will be the
quartic polynomials given in Example 2 in the Introduction, having cluster
size 2. Then we proceed as in part (a).

Remark: Our procedure does not yield irreducible polynomials of degree $2n$
having root clusters of size $n$ when $n$ is odd.

## References

  * [1] A. Perlis, Roots appear in quanta, The American Mathematical Monthly, Vol.111(4), 2004, pp. 61–63.
  * [2] P. Morandi, Field and Galois Theory, Graduate Texts in Mathematics 166, Springer, 1996.
  * [3] N Jacobson, Basic Algebra II, 2nd ed. 1989 W.H.Freeman, San Francisco (also Dover ed. 2009, and Hindustan Publishing Corporation, Delhi, India).
  * [4] M Filaseta, T Kidd, O Trifonov, Laguerre poynomials with Galois group $A_{m}$ for each $m$, Journal of Number Theory, 132 (2012) 776–1805.