Ứng dụng giải thuật di truyền cho tối ưu lịch trình mạng cảm biến không dây theo thời gian
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
Ứng dụng giải thuật di truyền cho tối ưu lịch trình mạng cảm biến không
dây theo thời gian
Application of Genetic Algorithm in Time-Based Wireless Sensor Network Schedule Optimization
Hà Văn Phương1,2*, Đào Trung Kiên1, Phạm Thị Ngọc Yến1, Lê Minh Hoàng1
1Trường Đại học Bách khoa Hà Nội, Hà Nội, Việt Nam
2Trường Đại học Công nghiệp Hà Nội, Hà Nội, Việt Nam
*Email: Havanphuong@haui.edu.vn
Tóm tắt
Trong những năm gần đây, mạng cảm biến không dây ngày càng được đặt biệt quan tâm, nghiên cứu và
ứng dụng mạnh mẽ trong nhiều lĩnh vực. Một vấn đề của mạng cảm biến là sự hạn chế về tài nguyên và
năng lượng hoạt động nên đã hạn chế rất nhiều tiềm năng ứng dụng của nó. Tối ưu hóa mạng cảm biến là
một lớp bài toán rất đa dạng và phong phú, trong đó lập lịch cho mạng cảm biến góp phần quan trọng giúp
tiết kiệm năng lượng và tăng thời gian hoạt động của mạng trong các ứng dụng thực tiễn. Tuy nhiên, việc tối
ưu hóa lập lịch cho mạng cảm biến là một bài toán rất phức tạp với nhiều ràng buộc, khó để giải quyết bằng
phương pháp giải tích. Bài báo này đề cập đến một phương pháp sử dụng thuật toán di truyền (GA) để tìm
ra giải pháp tối ưu lịch trình mạng. Việc tính toán giá trị hàm mục tiêu, đánh giá và lựa chọn dựa trên khả
năng thích nghi kết hợp các phép toán lai ghép và đột biến nhằm tiến hóa các cá thể trong quần thể qua các
thế hệ theo hướng tối ưu. Nghiên cứu đã đưa ra được mô hình bài toán tối ưu lịch trình theo thuật toán di
truyền và thực hiện được một số mô phỏng cho lịch trình tối ưu mạng cảm biến và dung lượng pin của các
nút với lịch trình tối ưu.
Từ khóa: Mạng cảm biến, tối ưu hóa lịch trình, thuật toán di truyền, tiết kiệm năng lượng.
Abstract
In recent years, wireless sensor networks (WSN) have been particularly interested, studied and applied very
strongly. A sensor network is generally limited in resources and energy, which greatly restrict its applicability.
Sensor network optimization in practice is a very diverse with a wide range of applications, whereas sensor
network scheduling is important in lowering energy consumption and maximizing network lifetime. However,
optimization of sensor network schedule is a very complex problem with many constraints that is not trivial to
solve by analytical methods. This paper discusses a heuristical approach using a genetic algorithm to find an
optimal solution for network scheduling. The evaluation of fitness function, as well as selection with
crossover and mutation operations help to evolve individuals in the population through generations in an
optimal direction. The modeling of a genetic algorithm for the schedule optimization is presented, and
simulation results with the optained optimal schedule are given.
Keywords: Sensor network, schedule optimization, genetic algorithm, energy efficiency.
Trong những năm gần đây, mạng cảm biến
giải pháp nhằm tiết kiệm năng lượng, kéo dài tuổi thọ
và nâng cao hiệu năng mạng.
không dây được quan tâm, nghiên cứu và ứng dụng
rất mạnh mẽ trong nhiều lĩnh vực như giám sát môi
quân sự và trong các ứng dụng dân dụng. Nhờ những
ưu điểm như không cần dây cấp nguồn và dây tín
hiệu, tính mềm dẻo linh hoạt, khả năng tùy biến cao,
dễ triển khai trên diện rộng và trong các môi trường
phức tạp, mang lại hiệu quả cao về kinh tế nên mạng
cảm biến không dây ngày càng được ứng dụng rộng
rãi. Tuy nhiên, một vấn đề lớn được quan tâm đối với
mạng cảm biến không dây là năng lượng cung cấp
cho các nút cảm biến rất hạn chế nên cần phải có các
Nghiên cứu, phát triển và ứng dụng mạng cảm
biến trong thực tế có rất nhiều mục tiêu. Nhiều bài
toán tối ưu hóa cho mạng cảm biến cần thực hiện như
tối ưu hóa năng lượng tiêu thụ, tối ưu hóa vùng phủ
sóng, tối ưu hóa kết nối mạng, tối đa hóa thời gian
hoạt động của mạng, v.v… Các tiêu chí trong mỗi
mục tiêu tối ưu hóa cũng được xác định khác nhau, ví
dụ trong tối đa hóa thời gian hoạt động thì tiêu chí về
thời gian hoạt động cũng được xác định khác nhau, có
thể mạng được coi là hoạt động khi chỉ cần một vài
nút còn hoạt động, hoặc khi phạm vi bao phủ của nó
trên một ngưỡng cho trước, hoặc bao phủ được những
thường không đồng nhất, các cảm biến đa dạng về
chủng loại, số lượng nút cảm biến lớn, không gian
triển khai mạng rộng, địa hình và môi trường phức
tạp, nên lập lịch hoạt động cho mạng cảm biến là một
ISSN: 2734-9381
Received: February 02, 2021; accepted: April 05, 2021
29
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
giải pháp được sử dụng phổ biến trong việc thực hiện
cấp dựa trên cụm. Các nút cảm biến trong mạng được
tổ chức thành các cụm, trong đó có trưởng cụm đóng
vai trò liên lạc với các cảm biến trong cụm của nó rồi
sau đó liên lạc với các trưởng cụm khác và trạm gốc,
còn các nút trong cụm có thể hoạt động hoặc ngủ tùy
thuộc vào tính cần thiết cụ thể tại một thời điểm. Như
vậy, các trưởng cụm sẽ có nhiều trách nhiệm hơn và
tiêu tốn nhiều năng lượng hơn, dẫn đến các cụm
trưởng sẽ có thể hết năng lượng và ngừng hoạt động
trước nhất ảnh hưởng chung toàn mạng. Để tránh tình
trạng này, các thuật toán lập lịch sẽ chia hoạt động
của mạng thành các chu kỳ, mỗi chu kỳ sẽ lựa chọn
biến đều có xác suất trở thành trưởng cụm ở chu kỳ
tiếp theo. Hơn nữa, số lượng trưởng cụm cũng phải
được xem xét trong vấn đề phân cụm, nếu số lượng
trưởng cụm nhiều quá mức cần thiết trong mạng thì
cũng gây lãng phí năng lượng của mạng vì vậy trong
thuật toán thiết lập lịch hoạt động cho mạng cần phải
xem xét việc xác định số lượng cụm trưởng cần thiết.
Lập lịch có thể dựa trên việc giám sát năng lượng
cụm sẽ được trưởng cụm giám sát và điều khiển việc
ngủ và thức tùy thuộc theo mức năng lượng tương đối
của nó trong cụm ví dụ mức năng lượng càng ít thì
được ngủ càng nhiều, trưởng cụm giám sát cũng được
lựa chọn lại ở mỗi đầu chu kỳ hoạt động của mạng.
các mục tiêu tối ưu hóa cho mạng. Lập lịch tối ưu cho
mạng cảm biến phụ thuộc vào mục tiêu cần tối ưu hóa
và các ràng buộc của mạng. Đây là bài toán tối ưu
hóa tổ hợp đa mục tiêu với nhiều ràng buộc phức tạp
rất khó để giải quyết bằng các thuật toán tối ưu xác
định hay phương pháp tích phân. Bài báo này đề cập
tới cách tiếp cận vấn đề này bằng cách sử dụng thuật
toán di truyền (GA) như một cơ chế tìm kiếm chung
cho giải pháp tối ưu tổng thể cho mạng cảm biến.
2. Bài toán tối ưu lịch trình cho mạng cảm biến
Do tính chất đa dạng và phức tạp về yêu cầu của
các bài toán ứng dụng mạng cảm biến, nên bài toán
tối ưu lịch cho mạng cảm biến cũng rất đa dạng và
phức tạp. Các cơ chế lập lịch có thể cùng mục tiêu tối
ưu nhưng các điều kiện ràng buộc khác nhau thì cơ
chế lập lịch cũng khác nhau. Nhìn chung, các mục
tiêu tối ưu hóa trong mạng cảm biến thường đi cùng
với hai vấn đề chính là tổng hợp dữ liệu và tiết kiệm
năng lượng cho mạng. Vì vậy, việc lập lịch tối ưu cho
mạng sẽ dựa trên sự kết hợp giữa cơ chế hoạt động tại
mỗi nút cảm biến với các trạng thái hoạt động như
ngủ, đo lường, truyền thông và cơ chế hoạt động
chung của toàn mạng để thực hiện mục tiêu tối ưu
hóa bài toán cụ thể. Tuy nhiên, trong khi tất cả các
chiến lược đều có một mục tiêu thiết kế chung để tối
đa hóa tuổi thọ mạng, thì các cơ chế để thực hiện vấn
đề này cũng đa dạng như các kỹ thuật được sử dụng
trong triển khai mạng cảm biến do các giả định khác
nhau được xem xét trong bối cảnh của các ứng dụng
loại theo nhiều cách: tĩnh và động, tập trung và phân
tán, hợp tác dựa trên giao tiếp và ít giao tiếp, phân
cấp và không phân cấp, v.v.
Như vậy, bài toán tối ưu hóa lập lịch cho mạng
cảm biến có bản chất thời gian biểu là rời rạc, việc
tìm kiếm giải pháp tối ưu bằng phương pháp phân
tích là không phù hợp. Bài báo này hướng tới cách
tiếp cận vấn đề này bằng cách sử dụng các thuật toán
giải pháp tối ưu hóa mạng cảm biến.
3. Thuật toán di truyền cho bài toán tối ưu lịch
trình mạng cảm biến
Ví dụ, với cơ chế lập lịch trong mạng không
phân cấp, các nút cảm biến có vai trò mạng như nhau.
Các nút cảm biến sẽ tự quảng bá thông tin bản thân
như vị trí, mức năng lượng, thời gian đã làm việc liên
tục cũng như thăm dò, giao tiếp với các nút lân cận để
đưa ra các yêu cầu đối với các nút lân cận hoặc quyết
định hành động của bản thân như tiếp tục ngủ để tiết
kiệm năng lượng hay thức dậy làm việc để đảm bảo
chức năng, nhiệm vụ và mục tiêu của mạng. Hiện có
nhiều cơ chế lập lịch trong mạng không phân cấp
được các nghiên cứu đề xuất và áp dụng, như cơ chế
lập lịch tối đa hóa về tuổi thọ mạng cảm biến với các
vấn đề hạn chế về thời lượng của pin và phạm vi cảm
trợ, dựa trên việc mỗi nút trong mạng tự động và định
kỳ đưa ra quyết định bật hay tắt bằng cách sử dụng
thông tin phủ sóng của các nút lân cận, một nút quyết
định tắt nó khi phát hiện ra rằng các nút lân cận có
thể giúp nó giám sát toàn bộ khu vực hoạt động của
biến phân cấp cũng tương tự như cơ chế lập lịch
không phân cấp, có nhiều cơ chế lập lịch khác nhau
đã được các nhóm nghiên cứu đề xuất và phát triển,
chẳng hạn như các cơ chế lập lịch trong mạng phân
3.1. Tổng quan thuật toán di truyền
Theo học thuyết Charles Darwin về tiến hóa của
các loài, trong tự nhiên, một quần thể bao gồm các cá
thể sinh sống và cạnh tranh nhau về nguồn tài nguyên
sống như thức ăn, nơi ở và các cá thể còn cạnh tranh
nhau trong vấn đề sinh sản và duy trì nòi giống.
Những cá thể có năng lực cao sẽ có khả năng sống sót
cao và có số lượng con cái lớn hơn, các cá thể yếu
hơn sẽ có ít con cái thậm chí không có con. Các thế
hệ sau sẽ được thừa hưởng, kết hợp và phát triển
những đặc điểm tốt từ bố mẹ nên con cái sẽ có năng
lực cao hơn bố mẹ rất nhiều. Đây chính là cách mà
các loài tiến hóa để thích nghi với môi trường sống.
Thuật toán di truyền bắt chước tự nhiên với các
nguyên lý tiến hóa như di truyền, chọn lọc tự nhiên,
lai ghép và đột biến để tìm ra giải pháp tối ưu tổng
thể cho một vấn đề, đặc biệt trong các bài toán liên
quan đến vấn đề tìm kiếm hoặc tối ưu hóa. GA hoạt
động với một tập hợp các cá thể, mỗi cá thể đại diện
một giải pháp khả thi cho vấn đề nhất định và có một
giá trị tùy thuộc vào mức độ giải quyết vấn đề đó.
30
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
Những cá thể có tính phù hợp cao sẽ được lựa chọn
•
Tạo quần thể mới: nếu điều kiện chấm dứt
không được thỏa mãn, quá trình sẽ tiếp tục bằng
cách tạo ra thế hệ mới theo hướng chất lượng
của nó được cải thiện so với thế hệ bố mẹ. Bước
này còn được gọi là sinh sản và đạt được bằng
cách thực hiện ba phép toán: lựa chọn, lai ghép
và đột biến trên quần thể hiện tại.
và lai với nhau để tạo ra thế mới có năng lực tốt hơn
bố mẹ. GA thường được ứng dụng cho những bài tối
Do những ưu điểm vượt trội, thuật toán di truyền
ngày càng được phát triển và ứng dụng mạnh mẽ
trong thực tế. GA đã được sử dụng trong tối ưu hóa
cho mạng cảm biến, một bài toán rất phổ biến và
quan trọng là tối ưu cơ chế lập lịch thực hiện các mục
tiêu tối ưu hóa trong mạng cảm biến.
- Lựa chọn hai cá thể bố mẹ từ quần thể cũ theo
độ thích nghi của chúng, cá thể có độ thích nghi
càng cao thì càng có nhiều khả năng được chọn.
- Lai ghép hai cá thể bố mẹ để tạo ra một cá thể
mới với một xác suất lai ghép được chọn.
Việc thực hiện một thuật toán di truyền điển
hình có thể được biểu diễn bằng lưu đồ được mô tả
trong Hình 1. Khi khởi tạo, một quần thể tạo được tạo
ngẫu nhiên. Sự ngẫu nhiên hóa này có thể hoàn toàn
đồng nhất hoặc đôi khi dựa trên một cá thể hạt giống
được người dùng cung cấp như một đầu vào của thuật
toán.
- Đột biến nhằm mục đích biến đổi ngẫu nhiên
một phần gen của cá thể mới với một xác suất
đột biến được chọn.
•
Kết thúc: nếu điều kiện dừng được thỏa mãn thì
thuật toán kết thúc và trả về lời giải tốt nhất
trong quần thể hiện tại.
Bắt đầu
Tuy nhiên, thứ tự của các bước trên này có thể
khác nhau hoặc thậm chí chúng có thể được kết hợp
theo các cách khác nhau trong một số biến thể của
thuật toán để có sự linh hoạt hơn trong việc triển khai.
Khởi tạo quần thể
ban đầu
3.2. Tối ưu lịch trình mạng cảm biến với thuật toán
di truyền
Tính giá trị hàm
thích nghi
Với các bài toán tối ưu hóa, điều quan trọng
nhất là hàm mục tiêu, có thể được biểu diễn chung
bằng một hàm toán học nhiều biến ánh xạ các phần tử
từ miền đầu vào X thành số thực:
Đ
( )
ꢀ ꢁ : ꢂ → R
(1)
Điều kiện dừng ?
trong đó x ∈ X là vectơ biến. Thông thường, X là tập
con của các phần tử trong Rn thỏa mãn các ràng buộc.
Đối với bài toán cực tiểu, một nghiệm x0 là một phần
S
Nhiễm sắc thể
Lựa chọn
(
)
tử mà ꢀ ꢃ0 ≤ ꢀ(ꢃ) với mọi x ∈ X.
của cá thể tốt nhất
Đối với bài toán tối ưu lịch mạng cảm biến, gốc
lõi vấn đề là lập lịch tối ưu cho từng nút mạng với các
ràng buộc liên quan để được lịch trình tối ưu cho toàn
mạng. Mỗi nút cảm biến sẽ hoạt động ở các chế độ
khác nhau như ngủ, chờ, đo lường, truyền thông,…
Trong bài toán này, tập hợp các chế độ của nút i được
biểu thị là Mi. Khi đó, một lịch trình của nút i được
xác định bởi một chuỗi:
Lai ghép
Đột biến
Kết thúc
Hình 1. Lưu đồ thuật toán di truyền.
ꢅ
ꢅ
〈
〉
ꢄ ≜ ꢆꢇ |ꢇ=1..ꢈ
,
(2)
gồm các bước cơ bản sau:
trong đó s là độ dài của chuỗi hay số lần thay đổi
trạng thái của nút, mij ∈ Mi là chế độ được sử dụng ở
trạng thái thứ j của nút i. Lịch trình của toàn mạng ꢄ
sẽ là sự kết hợp của các lịch trình của mọi nút trong
mạng gồm n nút. Chú ý rằng các các nút có cùng thời
gian bắt đầu là t0 = 0 và cùng thời điểm kết thúc cho
một lịch trình là T.
•
•
Bắt đầu: nhận các tham số cho thuật toán.
̂
Khởi tạo: sinh ngẫu nhiên một quần thể gồm n
cá thể.
•
•
Thích nghi: tính toán giá trị hàm thích nghi cho
từ cá thể trong toàn quần thể.
ꢅ
̂
{ }
ꢄ = ꢄ |ꢅ=1..ꢉ
(3)
Đánh giá: kiểm tra điều kiện kết thúc giải thuật.
31
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
Trong nghiên cứu này, nhiễm sắc thể mã hóa
lịch trình mạng ꢄ được định nghĩa như sau:
tối đa của pin. Nhóm đã phát triển và thực nghiệm 3
nút cảm biến đo nhiệt độ và độ ẩm không khí trong
các nút trong mạng thực nghiệm được đưa ra như
trong Bảng 1. Các mô phỏng được thực hiện bằng
nền tảng mô phỏng đã được nhóm nghiên cứu phát
̂
C = [m11,m12 ,…,m1s ,
m12 ,m22 ,…,ms2 ,
…
Bảng 1. Tham số các nút mạng của kịch bản
m1n ,m2n ,…,msn ]. (4)
Tham số
Nút 1 Nút 2 Nút 3
Dung lượng pin tối đa (mAh)
Tốc độ sạc pin (W)
3500 5250 7000
Số gen của mỗi nút là s và của toàn mạng là
(n×s). Giả sử quần thể có p cá thể, khi đó C|q=1..p
q
0.8
0.8
0.8
biểu thị lịch trình của cá thể q trong quần thể lịch
Mức tiêu thụ ở chế độ ngủ (W)
0.05 0.05 0.05
q
Mức tiêu thụ năng lượng trung
bình ở chế độ chờ (W)
q
0.17 0.17 0.17
thị đoạn gen trong C tương ứng lịch trình của nút i
trong lịch trình mạng q. Tương tự, tất cả các biến phụ
Mức tiêu thụ năng lượng trung
bình ở chế độ đo lường (W)
0.22 0.22 0.22
13.27 13.27 13.27
thuộc cá thể khác cũng tuân theo quy ước ký hiệu
ꢅ
q
này, ví dụ, ꢆꢇ là trạng thái j của nút i của cá thể q.
Lịch trình của nút i được biểu diễn như sau:
Mức tiêu thụ trung bình ở một lần
truyền thông (W)
qCi = [q m1i , q m2i , …, q msi ].
(5)
5
5
5
Δτ (phút)
T (ngày)
3
3
3
q
Theo đó, lịch trình của mạng gồm n nút C sẽ
Ngoài ra, trong kịch bản mô phỏng, vị trí, tọa độ
của nút trong không gian cũng cần được quan tâm và
xác định cụ thể vì nó liên quan đến vấn đề thu năng
lượng. Để tối đa hoá số lần đo thực hiện được của
mạng, đồng thời đảm bảo các yếu tố về năng lượng
và thời gian hoạt động, hàm mục tiêu được sử dụng là
một hàm gồm 4 thành phần:
được biểu diễn như sau:
qC = [qC1, qC2,…, qCn ].
(6)
qi
qt1i qt2i qt3i
qt4i
qt5i qt6i qt7i
qt8i
Φ = Φ1 + Φ2 + Φ3 + Φ4 ,
(7)
trong đó, Φ1 là thành phần tương ứng với số lần đo
cần tối đa hoá, Φ2 là thành phần giúp hạn chế các
Hình 2. Biểu diễn lịch trình hoạt động của một nút.
4. Kịch bản và kết quả mô phỏng
khoảng thời gian dài mà không có phép đo nào được
thực hiện, Φ3 để hạn chế việc các nút bị hết pin trước
Trong khuôn khổ bài báo này, một kịch bản thử
nghiệm thuật toán di truyền cho lớp bài toán tối ưu
lịch trình mạng với mục tiêu cụ thể là tối đa hóa số
giá trị đo thông số môi trường, với ràng buộc là tuổi
thọ của nút và đảm bảo thời gian giữa hai lần đo liên
tiếp không lớn hơn Δτ cho trước. Đối với mỗi nút
cảm biến, cần phải biết trước các thông số về năng
lượng tiêu thụ của nút như dung lượng lớn nhất của
pin, tốc độ sạc pin, năng lượng tiêu thụ của từng chế
độ làm việc. Thực tế, các nút cảm biến có thể có
nhiều chế độ làm việc như ngủ, chờ, đo lường và
truyền thông,… Tuy nhiên, trong bài toán này ràng
buộc là tối đa tuổi thọ mạng nên vấn đề năng lượng
tiêu thụ được đặc biệt quan tâm. Vì vậy trong kịch
bản này, để đơn giản, mỗi nút sẽ được xem xét với 2
chế độ là chế độ là ngủ M- tiêu thụ năng lượng ở mức
thấp và chế độ hoạt động M+ tiêu thụ năng lượng ở
mức cao. Như vậy Mi = {M-, M+}. Giả sử thời gian
toàn lịch trình được chia thành các khoảng bằng nhau
và mỗi khoảng là τ, khi đó τ×s = T.
khi kết thúc kịch bản chạy, và Φ4 để hạn chế việc mức
pin cuối chu kỳ mô phỏng nhỏ hơn khi bắt đầu. Cụ thể,
Φ1 = −kηη,
(8)
η
Φ = k ∆τ + k ∆τ 2 ,
(9)
∑
2
τ1
i
τ 2
i
i=1
2
Φ3 = kT1 T −T + k T −T
,
(10)
(11)
T 2
2
k
L − L + k L − L
if Le < Ls ,
(
)
(
)
L1
e
s
L2
e
s
Φ =
4
0 if L ≥ L ,
e
s
trong đó
η
là số lần đo thực hiện được; ∆τi là thời
gian giữa hai lần đo liên tiếp;
là thời điểm nút bị hết
T
pin, hoặc bằng
nếu không hết; Ls và Le là các mức
T
pin khi bắt đầu và kết thúc chu kỳ; và kη
kT1 kT 2 kL1 kL2 là các hệ số với giá trị hằng. Các
hàm bậc hai sử dụng cho Φ2−4 nhằm giúp thuật toán
kτ1 kτ 2
, , ,
Kịch bản thử nghiệm với mạng gồm 3 nút cảm
biến. Để đơn giản, giả sử rằng các nút có cấu hình
tương tự nhau và chỉ có sự khác biệt về dung lượng
,
,
,
32
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
5
100
90
80
70
60
50
40
30
20
10
0
10
3.5
3
2.5
2
1.5
1
Node
Node
Node
1
2
3
0.5
0
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
80
90
100
Time (h)
Generation
Hình 3. Giá trị thích nghi tốt nhất sau 100 thế hệ.
Hình 4. Dung lượng pin các nút với lịch trình tối ưu.
1000
Node
Node
Node
Total
1
2
3
900
800
700
600
500
400
300
200
100
0
0
5
10
15
20
0
10
20
30
40
50
60
70
Time (h)
Time (h)
Hình 5. Lịch trình mạng tối ưu.
Hình 6. Số phép đo thực hiện được theo thời gian.
hội tụ nhanh hơn. Giá trị các tham số chính của thuật
5. Kết luận
Trong nghiên cứu này, nhóm tác giả đã thực
hiện tìm hiểu, phân tích và xác định việc tối ưu hóa
lịch trình làm việc cho mạng cảm biến là bài toán rất
quan trọng liên quan đến vấn đề năng lượng, tuổi thọ
và hiệu năng mạng. Theo hướng tiếp cận ứng dụng
thuật toán di truyền cho bài toán tối ưu hóa lịch trình
mạng cảm biến. Nghiên cứu đưa ra mô hình hóa toán
học bài toán tối ưu lịch trình theo thuật toán di truyền.
Kết quả chạy mô phỏng với kịch bản thử nghiệm cho
thấy giải thuật di truyền rất hiệu quả trong việc tìm ra
giải pháp tối ưu lịch trình mạng cảm biến.
Bảng 2. Tham số của giải thuật di truyền
Tham số
Kích thước quần thể
Tỉ lệ lựa chọn
Giá trị
100
20%
50%
40%
Tỉ lệ lai
Tỉ lệ đột biến
Với các tham số đã định cho các nút của mạng
và GA thực thi sau 100 thế hệ, kết quả nhận được giá
trị thích nghi tốt nhất là 3.57×104. Quá trình hội tụ
của cá thể tốt nhất trong từng thế hệ. Lịch trình mạng
Tài liệu tham khảo
[1] Srivastava N. (2010) Challenges of next-generation
wireless sensor networks and its impact on society.
Journal of Telecommunications, pp. 128-133
Theo lịch trình tối ưu thu được, phạm vi thời
gian hoạt động trong một ngày cho ba nút riêng lẻ là
39,6%, 38,5% và 40,5%, nhưng sự kết hợp của chúng
tạo ra mức độ bao phủ 91,7% thời gian trong ngày.
Phần trăm dung lượng pin của các nút khi được mô
số phép đo đã thực hiện của từng nút và toàn mạng
các nút thực hiện các phép đo 312, 315 và 325 riêng
lẻ, với tổng cộng là 952.
[2] Guinard, A., McGibney, A., & Pesch, D. (2009,
November) A wireless sensor network design tool to
support building energy management. In Proceedings
of the First ACM Workshop on Embedded Sensing
Systems for Energy-Efficiency in Buildings (pp. 25-
30). ACM.
[3] Ma, J., Lou, W., Wu, Y., Li, X. Y., & Chen, G. (2009,
April). Energy efficient TDMA sleep scheduling in
wireless sensor networks. In IEEE INFOCOM 2009
(pp. 630-638). IEEE.
33
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
[4] L. Wang, and X. Yang. “A survey of energy-efficient
[9] J. H. Holland, Adaptation in Natural and Artificial
Systems, The University of Michigan Press,
Michigan, 1975.
scheduling mechanisms in sensor networks,” Mobile
Networks and Applications, vol. 11, no. 5, pp. 723-
740, 2006.
[10] Lee, S. C., Tseng, H. E., Chang, C. C., & Huang, Y.
M. (2019). Applying Interactive Genetic Algorithms
to Disassembly Sequence Planning. International
Journal of Precision Engineering and Manufacturing,
1-17.
[5] Berman, P., Calinescu, G., Shah, C., & Zelikovsly, A.
(2005). Efficient energy management in sensor
networks. In Y. Xiao & Y. Pan (Eds.), Ad hoc and
sensor networks. Nova Science.
[6] Tian, D., & Georganas, N. D. (2002). A coverage-
preserving node scheduling scheme for large wireless
sensor networks. In Proceedings of the 1st ACM
International Workshop on Wireless Sensor Networks
and Applications (WSNA ’02) (pp. 32–41), Atlanta,
Georgia.
[11] Liu, T. K., Lin, S. S., & Hsueh, P. W. (2019).
Optimal design for transport and logistics of steel mill
by-product based on double-layer genetic algorithms.
Journal of Low Frequency Noise, Vibration and
Active Control, 1461348419872368.
[12] Al-Furhud, M. A., & Ahmed, Z. H. (2020). Genetic
Algorithms for the Multiple Travelling Salesman
Problem. International Journal of Advanced
Computer Science and Applications (IJACSA), 11(7),
553-560.
[7] Heinzelman, W. R., Chandrakasan, A.,
&
Balakrishnan, H. (2000, January). Energy-efficient
communication protocol for wireless microsensor
networks. In Proceedings of the 33rd annual Hawaii
international conference on system sciences (pp. 10-
pp). IEEE.
[13] Nguyễn, T. H., Lê, M. H., Đào, T. K., Hà, V. P., &
Phạm, T. N. Y. (2020). Thiết kế, chế tạo nút cảm biến
có khả năng tùy biến phục vụ nghiên cứu, phát triển
nền tảng mô phỏng mạng cảm biến. Tạp chí Khoa học
và công nghệ, 56(4), 26-30.
[8] He, T., Krishnamurthy, S., Stankovic, J. A.,
Abdelzaher, T., Luo, L., Stoleru, R. et al. (2004).
Energy-efficient surveillance system using wireless
sensor networks. In Proceedings of the 2nd
International Conference on Mobile Systems,
Applications, and Services (MobiSys ’04) (pp. 270–
283), Boston, Massachusetts.
[14] Ha, V.P., Dao, T.K., Le, M.H., Nguyen, T.H., and
Nguyen, V.T. 2020. Design and implementation of
an energy simulation platform for wireless sensor
networks. 2020 IEEE International Conference on
Multimedia Analysis and Pattern Recognition
(MAPR). Hanoi, Vietnam, Oct.
34
JST: Engineering and Technology for Sustainable Development
Vol. 1, Issue 2, April 2021, 029-034
35
7 trang
12/04/2022
7800
Bạn đang xem tài liệu "Ứng dụng giải thuật di truyền cho tối ưu lịch trình mạng cảm biến không dây theo thời gian", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- ung_dung_giai_thuat_di_truyen_cho_toi_uu_lich_trinh_mang_cam.pdf
