1 Application Scheduling with Multiplexed Sensing of Monitoring Points in Multi-purpose IoT Wireless

2025-04-27 0 0 546.54KB 14 页 10玖币

侵权投诉

Application Scheduling with Multiplexed Sensing

of Monitoring Points in Multi-purpose IoT Wireless

Sensor Networks

Mustafa Can C¸ avdar, Ibrahim Korpeoglu, and ¨

Ozg¨

ur Ulusoy

Abstract—Wireless sensor networks (WSNs) have many ap-

plications and are an essential part of IoT systems. The pri-

mary functionality of a WSN is gathering data from speciﬁc

points that are covered with sensor nodes and transmitting the

collected data to remote units for further processing. In IoT

use cases, a WSN infrastructure may need to be shared by

many applications, which requires scheduling those applications

to time-share the node and network resources. In this paper,

we investigate the problem of application scheduling in WSN

infrastructures. We focus on the scenarios where applications

request a set of monitoring points to be sensed in the region

a WSN spans and propose a shared-data approach utilizing

multiplexed sensing of monitoring points requested by multiple

applications, which reduces sensing and communication load on

the network. We also propose a genetic algorithm called GABAS,

and three greedy algorithms for scheduling applications onto a

WSN infrastructure considering different criteria. We performed

extensive simulation experiments to evaluate our algorithms and

compare them to some standard scheduling methods. The results

show that our proposed methods perform much better than the

standard scheduling methods in terms of makespan, turnaround

time, waiting time, and successful execution rate metrics. We also

observed that our genetic algorithm is very effective in scheduling

applications with respect to these metrics.

Index Terms—wireless sensor networks, Internet of Things,

application scheduling, algorithms.

I. INTRODUCTION

WIRELESS sensor networks (WSNs) have become the

key components of Internet-of-Things and smart envi-

ronments due to improvements in sensing technologies, wire-

less communications, and mobile computing. Wireless sen-

sor networks are heterogeneous systems consisting of sensor

nodes that can collect different types of data from the points

within their sensing range. The collected data can be processed

at sensor nodes or higher-level distributed or centralized units,

like base stations or cloud data centers.

The application types of WSNs are very broad. Some

domains include smart cities, smart houses, and some other

intelligent systems that are used in daily life. Smart city man-

agement is one of the major areas for which WSN applications

are very useful. Intelligent parking systems [1] and noise

monitoring in metropolitan areas [2] are two examples of the

applications that a smart city can make use of. Other examples

M. C. C¸ avdar, I. Korpeoglu and ¨

O. Ulusoy are with the Department of

Computer Engineering, Bilkent University, Cankaya, Ankara, 06800, Turkey.

E-mail: mustafa.cavdar@bilkent.edu.tr, korpe@cs.bilkent.edu.tr,

oulusoy@cs.bilkent.edu.tr

of WSN applications include disaster prevention systems, agri-

culture management, habitat monitoring, intelligent lighting

control, and supply-chain monitoring [3].

Previously, WSNs were task-speciﬁc. A WSN was designed,

developed, and optimized to support a single application.

Another application deployment was impossible; therefore,

most WSN resources were underutilized. However, recently,

WSNs are started to be designed in a way that they can support

multiple applications, similar to other systems. For instance,

to a single city-wide WSN infrastructure, various types of

applications such as air quality monitoring, noise monitoring,

and crime detection can be deployed. Another example would

be a single building-wide WSN, which can be used for both

structural health monitoring [4] and ﬁre disaster detection [5]

at the same time. Various other applications can be run over

such a WSN infrastructure, such as occupancy estimation and

automatic air-conditioning control, without disturbing other

applications.

For a WSN that can handle multiple applications, it is

essential that the WSN is designed and operated in such a way

that applications get good quality of service and application

owners are well satisﬁed. Achieving this usually requires a

centralized mechanism and related policies. Software-Deﬁned

Networking (SDN) provides a mechanism that allows man-

aging a WSN from a centralized controller [6]. SDN also

enables virtualization that allows sharing physical resources

among multiple services, tasks, or applications. Therefore,

SDN is an essential component of next-generation networks

and Internet-of-Things [7]. With the help of SDN, applications

can be scheduled and placed onto IoT-integrated WSNs with

centralized algorithms in an efﬁcient and effective way.

In WSNs that support running multiple applications over

the same physical network, different applications may want

the same data type (e.g., temperature, image) to be collected

from the same points in the monitored area. For instance,

there may be two applications, one of which monitors trafﬁc

density at a point and the other one measures the average

speed of the vehicles between two points. The data collection

frequency of these two applications may not be equal to each

other, i.e., measuring average speed requires more frequent

data collection than monitoring trafﬁc density; however, both

applications require the same type of data. Therefore, we

propose a shared-data approach with multiplexed sensing

for running multiple applications on a WSN. Our approach

enables applications to share data from common monitoring

points in the most efﬁcient way, reducing the sensing and

arXiv:2210.06393v1 [cs.NI] 12 Oct 2022

communication load incurred on WSNs. Even though the

processing requirement will not change, the network will have

more sensing and communication resources available to admit

and schedule more applications simultaneously. This will help

reduce the total execution time of a set of applications and

also the waiting time of the newly arriving applications.

In this paper, we focus on the management of a WSN

operated by a single infrastructure provider. The network is

available to application providers who want their applica-

tions to be admitted to the network for a certain amount

of time. Admitted applications need some points monitored

with speciﬁc data types, and the collected data from those

points need to be processed in base stations and centralized

units. While we focused on the application placement problem

in our previous work [8] in a similar network structure, in

this work, we deal with the application scheduling problem.

Since the applications will use the network’s resources for a

particular time, it is crucial to schedule the applications (i.e.,

arrange the order of the admission of the applications into

the network) efﬁciently and effectively. One of the critical

parameters to minimize is the total execution time (makespan)

of the applications, but there are other metrics that can be

important, like average waiting time, turnaround time, and rate

of completing the applications before deadlines, if any.

We propose several algorithms for application scheduling in

wireless sensor networks. We ﬁrst propose a genetic algorithm

called GABAS that effectively schedules applications onto

a sensor network. GABAS reduces the total execution time

of the applications by both assigning monitoring points TO

sensor nodes and base stations and determining the admission

order in the best possible way. We also propose three greedy

algorithms, considering different criteria, which can be used

when fast decisions are needed.

We conducted extensive simulation experiments to evalu-

ate and compare our algorithms with well-known standard

scheduling algorithms. Experimental results show that GABAS

is very effective in ﬁnding an admission order for applications,

reducing total execution time. It also performs very well in

other metrics such as average turnaround time, average waiting

time, and successful completion ratio. Proposed greedy algo-

rithms, on the other hand, are very fast and effective compared

to other standard scheduling algorithms.

The rest of the paper is organized as follows: Section II

gives and discusses the related work in literature. Section III

presents our network model and problem formulation. Section

IV describes our approach and algorithms in detail, and

Section V provides the results of our simulation experiments.

Finally, Section VI concludes the paper.

II. RELATED WORK

Scheduling problem exhibits itself in all types of computer

systems and networks, where resources are limited and there

are tasks, applications, or services that need to time-share those

resources. The resources can be the processors of a computer,

the sensing and communication units of a wireless sensor

network, the physical servers and switches of a cloud data

center, or the edge computing nodes of a fog network.

There are many scheduling algorithms proposed in the

literature for processor and cloud scheduling [9]–[21]. They

use different meta-heuristics and evolutionary algorithms, such

as particle swarm optimization, genetic algorithms, and ant

colony optimization. Some of them also use greedy approaches

or classical approaches for scheduling, such as ﬁrst come ﬁrst

served, and shortest job ﬁrst algorithms. The metrics they

usually use include makespan, average response time, energy

efﬁciency, utilization, execution cost, and average running

time. They schedule tasks, jobs, or virtual machines on local

or cloud computing components, like physical servers.

There are also studies on scheduling in WSNs, IoT, fog,

and edge computing. Fog and edge computing are usually

integrated with WSNs in IoT systems. Porta et al. [22] propose

EN-MASSE, a framework that deals with dynamic mission

assignment for WSNs whose sensor nodes have energy har-

vesting capabilities. It is an integer programming method that

assigns missions to sensor nodes and aims to minimize the

total run-time of the missions. Uchiteleva et al. [23] describe

a resource scheduling algorithm for WSNs. The proposed

scheduling algorithm is a resource management solution for

isolated proﬁles in WSNs, and the authors compare their al-

gorithm with Round Robin and Proportionally Fair scheduling

algorithms. Wei et al. [24] present a Q-learning algorithm

called ISVM-Q for task scheduling in WSNs. It optimizes

application performance and total energy consumption. De

Frias et al. [25] propose an application scheduling algorithm

for shared actuator and sensor networks. Their algorithm aims

to reduce energy consumption in the network. Edalat and

Motani [26] propose a method for task scheduling and task

mapping in a WSN consisting of sensor nodes with energy

harvesting capabilities. They consider task priority and energy

harvesting to increase fairness.

Liu et al. [27] propose Horae, a task scheduler for mobile

edge computing. The scheduler aims to improve resource

utilization in the MEC environment as well as select the

edge server that satisﬁes placement constraints for each task.

Javanmardi et al. [28] present FUPE, a security-aware task

scheduler for IoT fog networks. It is a fuzzy-based multi-

objective Particle Swarm Optimization algorithm. The au-

thors show that it performs better than the other compared

algorithms in terms of average response time and network

utilization. Li and Han [29] describe an artiﬁcial bee colony

algorithm (ABC) for task scheduling in the cloud. The pro-

posed ABC algorithm is compared against several works

from the literature. The evaluation metrics they consider

are makespan, maximum device workload, and total device

workload. D’Amico and Gonzalez [30] propose EAMC, which

is a multi-cluster scheduling policy. It predicts the energy

consumption of jobs and aims to reduce makespan, response

time, and total energy consumption. Singhal and Sharma [31]

present a Rock Hyrax Optimization algorithm to schedule

jobs in heterogeneous cloud systems. They consider evaluation

metrics like makespan and energy consumption.

Choudhari et al. [32] propose a priority-based task schedul-

ing algorithm for fog computing systems. Their algorithm ﬁrst

assigns an arriving request to the closest fog server, placing

the task into a priority queue within that fog server. Xu et

al. [33] apply online convex optimization techniques to sched-

ule arriving jobs with multi-dimensional requirements in het-

erogeneous computing clusters. Psychasand and Ghaderi [34]

describe algorithms based on Best Fit and Universal Parti-

tioning to schedule jobs with various resource demands. Fang

et al. [35] aim to reduce total job completion time in edge

computing systems. They propose an approximation algorithm

for both ofﬂine and online scheduling. Arri and Singh [36]

describe an artiﬁcial bee colony algorithm that also makes use

of an artiﬁcial neural network for job scheduling in fog servers.

Our work in this paper differs from the studies mentioned

above with the following novel features:

•We propose GABAS, a novel genetic algorithm that

can schedule applications onto a WSN in an effective

manner. While admitting and scheduling an application,

our algorithm also decides which sensor and base stations

will be used to sense and process data from the moni-

toring points requested by the application. Our genetic

algorithm performs very well in various metrics, such

as makespan, average turnaround time, average waiting

time, and successful completion ratio.

•We also propose three greedy algorithms, each of which

considers different criteria for ordering applications that

are feasible to admit. These algorithms are better suited

for scenarios where fast decisions are needed.

•We consider a network structure where certain points are

monitored by sensor nodes in a multiplexed manner so

that data can be shared and utilized by several appli-

cations at the same time. The sensing rate is adjusted

depending on the demands of the applications requiring

the common points to be sensed. The collected data

is processed in base stations, and also in data centers

if needed. In this way, sensing and communication re-

sources of a WSN are better utilized, allowing more

applications to be scheduled at the same time. We focus

on urban-area networks, where base stations can easily

be inter-connected with high-speed wired or wireless

networks.

III. PROBLEM STATEMENT

The sensor network type we consider in this paper is a

wireless sensor network (WSN) that is owned by a single

provider and covers an urban region (like a city or town).

Application owners require some points in the region to be

sensed and sensed data to be collected and processed in

cluster-heads. We assume the sensor network has a clustered

two-tier architecture, consisting of sensor nodes and cluster-

head nodes. We will call the cluster-head nodes also as base

stations throughout the paper since they will act like base

stations in a wireless network. They will be mains-powered

and connected to the wired or wireless backbone network of

a city. They will also be able to do local processing for the

incoming sensor data. In an urban environment, cluster-head

nodes can easily be mounted on top of the elements of the

city-wide infrastructure (like lamp poles); therefore, they can

easily be connected to the backbone network. In this way,

the use of cluster-heads in our architecture is different from

Fig. 1. Network model.

the classical WSN architectures, where cluster-heads are just

intermediate nodes on multi-hop paths from sensor nodes to

sink nodes. In an urban environment, we assume that each

sensor node can directly connect to one of the base stations

in its range. Each base station and the connected sensor nodes

form a star topology.

We assume sensor nodes have equal sensing rates but

various sensing ranges. Base stations have equal processing

capacity. Additionally, we assume that any link between a

sensor node and a base station has the same bandwidth

capacity. A sensor node can collect data from the monitoring

points which fall into its sensing range. The collected data

is processed, partially or totally, in the base stations. It is

possible that a base station can send the processed data further

to a centralized location for additional processing or analysis.

However, this part of the problem is not within the scope of

this paper. We assume the bandwidth of the links connecting

base stations to the rest of the network is abundant; hence

is not a constraint in our formulation. We only consider the

bandwidth capacity of connections between sensor nodes and

base stations as a constraint. Similarly, we assume that the

centralized servers have the abundant capacity to process the

incoming data if needed. Therefore, we only consider the

processing capacity of the base stations as a constraint in our

model.

Figure 1 shows an example of our network model. In the

ﬁgure, radio towers represent base stations (cluster-heads),

large circles represent sensor nodes and small circles represent

monitoring points. A dashed line between a sensor node and a

monitoring point indicates that the sensor node actively senses

the monitoring point. If a sensor node is connected to a base

station, there is a dotted line between the sensor node and the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1ApplicationSchedulingwithMultiplexedSensingofMonitoringPointsinMulti-purposeIoTWirelessSensorNetworksMustafaCanC¸avdar,IbrahimKorpeoglu,and¨Ozg¨urUlusoyAbstractWirelesssensornetworks(WSNs)havemanyap-plicationsandareanessentialpartofIoTsystems.Thepri-maryfunctionalityofaWSNisgatheringdatafromspeci...

展开>> 收起<<

1 Application Scheduling with Multiplexed Sensing of Monitoring Points in Multi-purpose IoT Wireless.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Application Scheduling with Multiplexed Sensing of Monitoring Points in Multi-purpose IoT Wireless

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: