Thuật toán điều phối tính toán giảm tiêu thụ năng lượng trong điện toán đám mây di động

: Năng lượng tiêu thụ để gửi và nhận dữ liệu của CCl Dl
 EM()NE--()LC . NP##C 2PTIP##LT- P
một nút di động theo đơn vị watt. Thông thường '1SM BL
việc truyền dữ liệu tiêu thụ điện cao hơn việc nhận (5)
dữ liệu, nhưng để đơn giản chúng tôi cho giả định Bây giờ chúng ta xem xét trường hợp các 
chúng tiêu thụ như nhau. lệnh CC được giảm tải trên cloudlet hoặc remote 
- MN: mobile node hoặc là thiết bị di động cloud. Để so sánh chúng ta thực hiện tính T(CR)- 
- LC: Local cloudlet T(LC) và E(CR)- E(LC) như dưới đây:
- RC: Remote cloud CM CCR D
 TC()RT-=()LC ++2NT# PR +
 Khi tất cả các tính toán được thực hiện trên ( SM SCR BR 2
một nút di động, tất cả các lệnh (C + C ) được 
 M C CM CCL D
thực hiện với tốc độ của S . Không có trao đổi dữ -+++2NT# PL
 M ( SM SCL BL 2
liệu. Vì vậy, thời gian hoàn thành T và năng lượng 
 Ta được 
tiêu thụ là E EC()RE- ()LC
 CC+
 MC R - V
 T(MN) = (1) S ##1 F +-+W
 SM SPCICl S 2()TTPR PL W (6)
 = N # S '1CR W
 CCMC+ S 11 W
 E(MN) = PC # (2) S+-PDT ##l W
 SM S blBBRL W
 T X
 Khi tất cả các lệnh CC được thực hiện trên Để các lệnh có thể giảm tải được thực thi 
cloudlet hoặc remote cloud, ngoài thời gian dành để trên cloudlet có lợi nhất cho mobile khi tất cả các vế 
thực thi lệnh, còn có thêm thời gian để trao đổi dữ phải của phương trình từ (5) đến (6) đều lớn hơn 0. 
liệu với kích thước D. Thời gian trao đổi dữ liệu bao Từ đó ta suy ra được 4 bất đẳng thức sau
gồm một thời gian truyền dữ liệu, được định nghĩa 
 CC’ > SM × (2TPL + D’/BL) (7)
là (kích thước dữ liệu/băng thông) và thời gian C > S × (2P × T + P × D’/B ) (8)
truyền dữ liệu giữa hai nút. Chúng tôi giả định rằng C’ M I PL T L
 CC’ < SCR × {2(TPR - TPL) + D’×(1/BR - 1/BL)}/(F-1) 
hoạt động ba bước Gửi dữ liệu - Xử lý – Nhận dữ (9)
liệu được lặp đi lặp lại N lần. Như vậy toàn bộ giai 
 CC’< SCR×{2(TPR-TPL)+(PT/PI)×D’×(1/BR-1/BL)}/(F-1) 
đoạn tính toán tương tác liên quan đến việc truyền (10)
dữ liệu 2N và đòi hỏi 2N × TP giây cho toàn bộ 
thời gian truyền nhận dữ liệu. Vì vậy, thời gian hoàn Để các lệnh có thể giảm tải được thực thi 
thành và năng lượng tiêu thụ tại các nút di động với trên cloud có lợi nhất cho mobile khi
các lệnh CC được giảm tải bởi CL hoặc CR là: C > S × (2T + D’/B ) (11)
 Giảm tải cho cloudlet C’ M PR R
 CC’ > SM × (2PI × TPR + PT × D’/BR) (12)
 CM CCL
 D CC’ > SCR × {2(TPR- TPL) + D’× (1/BR - 1/BL)}/(F-1) 
TL()C =+++2NT# PL (3.1)
 SM SCL BL (13)
 C >S ×{2(T -T )+(P /P )×D’×(1/B -1/B )}/(F-1) 
 CM CCL D C’ CR PR PL T I R L
 EL()CP=+C ##PI ++2NT##PL PT (14)
 SM dnSCL BL 
 (4.1)
 Giảm tải cho remote cloud Ngoài hai trường hợp trên thì việc giảm tải 
 sẽ không có lợi cho mobile. 
 CM CCR D
TR()C =+ ++2NT# PR (3.2) Để thực hiện các phân tích thuận lợi hơn, 
 SM SCR BR
 chúng tôi khảo sát dữ liệu thu thập từ một số di động 
 CM CCR D thực, các nút, mạng, và những đám mây và chọn số 
 ER()CP=+C ##PI ++2NT##PR PT
 SM dnSCR BR thực tế [2] cho một số trong những tham số được sử 
 (4.2) dụng trong các phương trình.
 Đầu tiên chúng ta xem xét trường hợp tất cả • SM: Bộ vi xử lý ARM Cortex A7 được 
các tính toán được thực hiện trên mobile và trường xử dụng trong rất nhiều mobile bao gồm cả 
hợp các lệnh CC được giảm tải tới cloudlet. Để so smartphones và máy tính bảng có tốc độ thực thi 
sánh thời gian hoàn hành và năng lượng tiêu thụ của lệnh là 2.85GIPS tại 1.5GHz
mobile trong cả hai trường hợp trên, chúng ta tính • SCR: bộ vi xử lý Intel Xeon được sử dụng 
T(MN)- T(LC) và E(MN) – E(LC) như dưới đây và phổ biến trong các máy chủ và bộ xử lý Xeon 5690 
chúng ta giả sử SCL >> SM. có tốc độ 84 GIPS tại 3.46GHz. Con số này là gần 
 30 lần tốc độ của ARM Cortex A7. Nhưng một máy 
 CCMC+ CM CCL D
TM()NT-=()LC -+++2NT# PL chủ cloud có hệ thống phân cấp bộ nhớ nhanh hơn 
 SM blSM SCL BL
 và hiệu suất cao hơn cho tính toán dấu chấm động 
52 Khoa học & Công nghệ - Số 13/Tháng 3 - 2017 Journal of Science and Technology
 ISSN 2354-0575
và có thể cung cấp số lượng nhiều hơn các lõi cho như trong Hình 2. Giả định mô hình di chuyển ngẫu 
một ứng dụng. Vì vậy, trong một thực tế, gia tốc của nhiên. Trong các hình chúng ta xem xét tham số 
một nút đám mây trên một thiết bị di động có thể dễ tỉ số tốc độ xử lý của cloud/cloudlet là 8. Đối với 
dàng vượt qua 100 ~ 150. dữ liệu trao đổi trong một quá trình đầu vào - xử 
 • SCL: Bởi vì một đám mây nhỏ có thể được lý - đầu ra, chúng tôi xem xét các kích thước 10kb, 
lắp ráp cùng một loại máy chủ off-the-shelf như 100kb. Số lượng các bước nhảy đại diện cho một 
trong một đám mây ở xa, tốc độ của mỗi máy chủ loạt các chuyển động của người dùng. Nếu nó là 
thành phần có thể gần như giống nhau. Nhưng một 1, người dùng không rời khỏi phạm vi của cloudlet 
đám mây nhỏ sẽ có ít số lượng máy chủ và mạng truy cập ban đầu. Nếu nó là 5, người dùng di chuyển 
vật lý nội bộ kết nối chúng và phần mềm hỗ trợ, xa như 4 bước nhảy ra khỏi phạm vi của cloudlet 
môi trường hoạt động có thể chậm hơn. Chúng ta truy cập ban đầu.
có thể gán cùng một số lõi để chạy một ứng dụng 
như trong một đám mây ở xa, mặc dù trong một 
đám mây nhỏ số lượng các ứng dụng thực thi cùng 
một lúc sẽ thấp hơn nhiều. Với những quan sát này, 
chúng tôi đoán rằng gia tốc của một đám mây trên 
một đám mây nhỏ sẽ không thể rất cao và chúng tôi 
giả định khoảng 2 ~ 16 và gọi gia tốc này là F.
 • BR: Một remote cloud ở xa được truy cập 
thông qua LTE sẽ có băng thông lớn nhất là 20Mbps.
 • BL: Một đám mây nhỏ địa phương được truy 
cập thông qua một mạng lưới không dây. Chúng tôi 
giả định rằng một bộ định tuyến truy cập sử dụng 
WiFi để truy cập các thiết bị di động và các thiết bị 
định tuyến truy cập lân cận. IEEE802.11n có băng 
thông 72.2 Mbps sử dụng 20 MHz. Giả sử khoảng 
40% thông lượng, chúng tôi chọn 30Mbps. 
 • TPR: hơn 90% người dùng trải nghiệm 
không lớn hơn độ trễ 25msec để truy cập trung tâm 
điện toán đám mây Amazon gần nhất thông qua Hình 2. Biểu đồ phân bổ tính toán
Internet. Và độ trễ truy cập Internet cho LTE là gần 
100ms. Vì vậy, chúng tôi chọn TPR là 120 mili giây. Ta thấy một người sử dụng có thể di chuyển 
 • TPL: Mặc dù thời gian trễ của WiFi có biến ra khỏi các bộ định tuyến truy cập ban đầu với số 
động cao, chúng tôi giả định một độ trễ /hop cho lượng các bước nhảy tùy theo dữ liệu trao đổi. Nếu 
WiFi là 20 ms. Vì vậy, nếu yêu cầu được gửi qua N kích thước dữ liệu tăng, phạm vi người dùng có 
đám mây nhỏ trong mạng lưới không dây, thì phải thể di chuyển xung quanh giảm. Chúng tôi tăng số 
mất 20*N ms. lượng hop đến 10, và chúng ta vẫn có thể tìm thấy 
 Bảng dưới đây cho ta biết số về mức độ tiêu các giá trị hợp lệ để giảm tải. Điều này có nghĩa 
thụ năng lượng trong các chế độ hoạt động của các rằng nếu kích thước dữ liệu trao đổi không phải là 
thiết bị mobile phổ biến hiện nay. quá lớn, người dùng có thể di chuyển rất xa các bộ 
 định tuyến truy cập ban đầu.
 Mobile Devices PC PI PT
 HP iPAQ PDA 400MHz 0.9 0.3 1.3 3. Thuật toán điều phối giảm tải cho mobile
 Quá trình điều phối giảm tải tính toán cho 
 Nokia N810 400MHz 0.8 1.5
 thiết bị di động được thực hiện tuần tự theo như 
 Openmoko Neo Freerunner 0.27 biểu đồ hình 3 dưới đây.
 Thiết bị di động gửi yêu cầu giảm tải đến 
 Galaxy S2 1.5 GHz 0.36 1.7
 cloudlet1, cloudlet 1 kiểm tra, gửi thông điệp chấp 
 Các thiết bị di động ngày các phát triển và nhận hoặc từ chối yêu cầu. Nếu chấp nhận yêu cầu, 
có xu hướng tiêu thụ nhiều năng lượng hơn. Do vậy thiết bị di động gửi dữ liệu giảm tại đến cloudlet1. 
trong thực nghiệm này chúng tôi chọn các thông số Cloudlet 1 thực hiện giảm tải hoặc chuyển tiếp yêu 
như sau: cầu đến vị trí giảm tại được xác định. Sau khi thực 
 PC: 1.0 watt ; PI: 0.3 watt; PT: 2.0 watts hiện xong, cloudlet thực hiện giảm tải sẽ gửi trả kết 
 Chúng tôi áp dụng các giá trị tham số đã quả lại cho thiết bị di động. 
giải thích ở trên cho (9) - (12) và thu được kết quả Để điều phối quá trình giảm tải chúng tôi 
Khoa học & Công nghệ - Số 13/Tháng 3 - 2017 Journal of Science and Technology 53
ISSN 2354-0575
xây dựng hai thuật toán là thuật toán 1 để xác định 2. for (i=0; I < Vn; i++)
vị trí giảm tải và thuật toán 2 để điều phối quá trình 1) If (HT(w ,n) < T ) and
giảm tải tới vị trí được xác định trong thuật toán 1. i request 
 (HE(wi,n) < Emin) then
 1.1) Emin = HE(wi,n)
 1.2) H=n
 2) end if
 3. next for
 4. return HMN
 Thuật toán CRA 2: Giảm tải cho một tập các 
 quá trình
 Input: Danh sách quá trình cần giảm tải W
 1. Xắp xếp danh sách theo trình tự thời gian 
 hoàn thành của các nhiệm vụ
 !
 2. while wi W do
 1) Yêu cầu thông tin về mobile node IMN
 2) Gọi CRA1 để Xác định vị trí giảm tải H 
 3) chuyển yêu cầu w đến vị trí H
 i
 4). i++
Hình 3. Biểu đồ quá trình điều phối xử lý các yêu 
 3. end while
 cầu từ Mobile device
 2.4. Kết quả kiểm tra 
 Mỗi nhiệm vụ giảm tải yêu cầu một số lượng 
 Tiếp theo, chúng tôi mô phỏng lần 1 với một 
các lệnh phải được xử lý tính toán theo thứ tự, nó 
 mạng gồm 10 cloudlet và 1000 yêu cầu gửi đến 
được cho bởi hàm I. Ví dụ I(t ) số lệnh của nhiệm 
 i trong thời gian 50000s. Kết quả được cho bởi biểu 
vụ t . Theo đó khi một nhiệm vụ được giảm tải trên 
 i đồ hình 4 dưới đây. 
cloudlet thì nhiệm vụ đó cần được chuyển đến 
 Chúng tôi mô phỏng lần 2 với một mạng 
cloudlet. Kích thước dữ liệu trong mỗi giao tiếp cho 
 gồm 20 cloudlet và 1000 yêu cầu gửi đến trong thời 
bởi hàm D. Theo đó chúng ta có D(t ) là kích thước 
 i gian 50000s. Kết quả được cho bởi biểu đồ hình 5 
của dữ liệu cần trao đổi giữa mobile và node thực 
 dưới đây.
hiện giảm tải.
 Chúng ta có thể nhận thấy: Số yêu cầu được 
 Cho đồ thị G(N,R) với các đỉnh là các node 
 gửi đến các cloudlet được thể hiện bằng đường màu 
(cloudlet) xử lý giảm tải, và các cạnh thể hiện 
 xanh lá cây. Khi không sử dụng thuật toán CRA các 
đường liên kết dữ liệu giữa các node, Một node xử 
 yêu cầu không thể chấp nhận thực hiện được thể 
lý n ! N phải là thiết bị di động hoặc là một cloudlet 
 hiện bằng đường màu xanh thẫm.
hoặc cloud nhưng trong cùng thời điểm không thể 
 , , 
ở nhiều hơn một nơi. Như vậy: N = NS NCL NRC 
 b
và NS ∩ NCL ∩ NRC = .
 Các cạnh là đường liên kết các node với 
nhau. Ta gọi hàm B(na, nb) là băng thông giữa node 
na và nb. Gọi S là hàm trả về tốc độ xử lý của mỗi 
node, ví dụ S(na) là tốc độ tính toán của node na.
 Gọi HE là hàm heuristic trả về giá trị ước 
tính năng lượng tiêu thụ cho mỗi nhiệm vụ khi thực 
thi tại mỗi node trong vùng phủ. Như vậy HE(wi,n) 
là năng lượng tiêu thụ của node n khi thực thi nhiệm 
vụ wi.
 Gọi HT là hàm heuristic trả về giá trị ước 
tính thời gian hoàn thành nhiệm vụ khi thực thi tại 
mỗi node trong vùng phủ. Như vậy HT(wi,n) là thời 
gian hoàn thành của node n khi thực thi nhiệm vụ wi
 Thuật toán CRA1: Xác định vị trí giảm tải Hình 4. Phân bố tính toán trên 10 cloudlet
 Input: Thông tin về mobile device, wi
 1. H ! null
54 Khoa học & Công nghệ - Số 13/Tháng 3 - 2017 Journal of Science and Technology
 ISSN 2354-0575
 Khi sử dụng thuật toán CRA các cloudlet có 
 thể chấp nhận thực hiện các yêu cầu được thể hiện 
 bằng đường màu đỏ, và không thể chấp nhận được 
 thể hiện bằng đường màu tím. Những yêu cầu này 
 có thể bị trả về hoặc chuyển đến đám mây ở xa. 
 Nhìn vào biểu đồ ta có nhận xét rằng: Khi sử dụng 
 thuật toán CRA các yêu cầu sẽ được phân bố cho 
 các cloudlet khá đồng đều để có thể chấp nhận tối 
 đa các yêu cầu gửi đến. Đồng thời số yêu cầu bị từ 
 chối hoặc chuyển đến cloud ở xa là ít hơn rất nhiều. 
 Điều này cũng có nghĩa khi các mạng đi động đều 
 sử dụng thuật toán phân bổ quá trình tính toán CRA 
 của chúng tôi thì Hệ thống mạng internet và các 
 Trung tâm dữ liệu đám mây ở xa sẽ được giảm khá 
 nhiều lưu lượng lưu thông và yêu cầu tính toán; Góp 
 phần tiết kiệm năng lượng cho toàn bộ hệ thống 
 internet. Hơn nữa việc chấp nhận các yêu cầu gửi 
 từ mobile tăng lên, đồng nghĩa với việc tăng cường 
 Hình 5. Phân bố tính toán trên 20 cloudlet chất lượng dịch vụ cho mạng di động.
Tài liệu tham khảo
 [1]. Yaser Jararweh, Fadi Ababneh, Abdallah Khreishah, Fahd Dosari, “Scalable Cloudlet-based 
 Mobile Computing Model”, Procedia Computer Science, Vol. 34, pp. 434-441, 2014.
 [2]. Ying-Dar Lin; Chu, E.T.-H.; Yuan-Cheng Lai; Ting-Jun Huang, “Time-and-Energy-Aware 
 Computation Offloading in Handheld Devices to Coprocessors and Clouds,” in Systems Journal, 
 IEEE, vol.9, no.2, pp.393-405, June 2015. 
 [3]. Yi-Bing Lin et al “Performance Measurement of TDLTE, WiMAX and 3G Systems,” IEEE 
 Wireless Communications, vol. 20, no. 3 pp. 153-160, June 2013.
 [4]. Y.-C. Shim, “Modeling and Analysis of Completion Time and Energy consumption of Applications 
 in Mobile Cloud Computing Environments,” Int. Journal of Advanced Computer Technology, vol. 
 3, no. 6, pp. 60-66, 2014.
 [5]. R. Bradford, E. Kotsovinos, A. Feldmann, and H.Schioberg, “Live Wide-Area Migration of 
 Virtual Machines including Local Persistent State,” VEE’07, June 2007. 
 [6]. E. Harney, S. Goasguen, J. Martin, M. Murphy, and M. Westall, “The Efficacy of Live Virtual 
 Machine Migrations over the Internet,” VTDC’07, November 2007.
 [7]. P. Payaswini and D.H. Manjaiah, “Simulation and Performance Analysis of Vertical Handoff 
 between WiFi and WiMAX using Media Independent Handover Services,” International Journal of 
 Computer Applications, vol. 87, no. 4, Feb. 2014.
 [8]. K. Kumar and Y.-H. Lu, “Cloud Computing for Mobile Users: Can Offloading Computation 
 Save Energy?” IEEE Computer, pp. 51-56, April 2010.
 [9]. A. Carroll and G. Heiser, “An Analysis of Power Consumption in a Smartphone,” USENIX 
 Annual Technical Conference, 2010. 
 AN COORDINATED ALGORITHM REDUCES ENERGY CONSUMPTION
 IN MOBILE CLOUD COMPUTING
Abstract:
 Technology of local small clouds (cloudlet) is potential for strong growth. The ability of small cloud 
technology enables service providers, application offload compute, storage with superior features than 
ever. However, the combination of cloudlet with mobile networks data center in practice requires more 
technological solutions. In this paper, we are interested in solutions to coordinate the process offloading 
Khoa học & Công nghệ - Số 13/Tháng 3 - 2017 Journal of Science and Technology 55
ISSN 2354-0575
calculations for mobile devices, which reduces the computational requirements of the data center to the 
mobile network. This lowers the needs to consume energy of the data center. We propose an algorithm of 
cooperation among small clouds, addressing the above issues effectively. The experimental results confirm 
that our solutions can significantly reduce energy costs and enhance the system’s ability to meet and improve 
service quality required by the users.
Từ khóa: Mobile network, small cloud, coordinated algorithm, cloudlet, MCC.
56 Khoa học & Công nghệ - Số 13/Tháng 3 - 2017 Journal of Science and Technology