Kĩ thuật lập trình - Quản lý di động

Quản lý di động Tính toán di động Quản lý di động 1. Giới thiệu 2. Quản lý vị trí 3. Quản lý chuyển giao 4. Ví dụ 03/10/2011 @Hà Quốc Trung 2011 2 1. Giới thiệu 03/10/2011 @Hà Quốc Trung 2011 3 I. Bài toán II. Quản lý vị trí III. Quản lý chuyển giao I. Bài toán 03/10/2011 @Hà Quốc Trung 2011 4  Điều kiện  Nút n muốn trao đổi thông tin với nút di động m  Nút m kết nối thông qua một điểm truy cập (AP) hoặc một trạm cơ sở (BS)  Để thống nhất, sử dụng thuật ngữ AP  Nút m có thể kết nối với một AP khác Yêu cầu 03/10/2011 @Hà Quốc Trung 2011 5  Nút n có thể thiết lập kết nối với m  => cần xác định vị trí của m: quản lý vị trí  Nút n có thể duy trì kết nối với m  Cần có cơ chế để thiết lập lại kết nối vật lý với m  Cần có cơ chế để duy trì kết nối logic  => quản lý chuyển giao (Handoffs) Ví dụ 03/10/2011 @Hà Quốc Trung 2011 6  Thanh toán tiền điện/điện thoại  Hóa đơn gửi đến nhà  Thanh toán tiền qua tài khoản/thu trực tiếp  Đi vắng  Nhờ thanh toán hộ  Chuyển nhà  Báo chuyển địa điểm (cho ai?) II. Quản lý vị trí 03/10/2011 @Hà Quốc Trung 2011 7  Các thao tác cơ bản  Tìm kiếm: tìm kiếm vị trí theo địa chỉ  Quảng bá  Quảng bá cục bộ  Cập nhật: cập nhật thông tin về vị trí khi có sự thay đổi  Đăng ký: ghi lại các thay đổi về vị trí với một server  Cập nhật, đăng ký, tìm kiếm=> hiệu năng  Tính cập nhật của thông tin, phạm vi của cell cục bộ Phạm vi của cell cục bộ 03/10/2011 @Hà Quốc Trung 2011 8  Nhỏ=>  Tìm kiếm bằng quảng bá nhanh và rẻ hơn  Thường xuyên phải cập nhật thông tin (do nút thường xuyên chuyển từ AP này sang AP khác)  Chi phí về lắp đặt AP tăng  Lớn  Phức tạp trong việc thiết lập kết nối cục bộ Kiến trúc CSDL 03/10/2011 @Hà Quốc Trung 2011 9  Cơ sở dữ liệu về vị trí  Co giãn, hiệu năng, sẵn sàng  Phân tán ở mức độ hợp lý  => mô hình quản lý vị trí III. Chuyển giao-Handoffs 03/10/2011 @Hà Quốc Trung 2011 10  Đảm bảo kết nối khi dịch chuyển từ máy này sang máy khác  Các gói tin được truyền-nhận cùng một thời điểm  Câu hỏi  Khi nào chuyển sang AP mới?  Chọn AP nào?  Giữ kết nối thế nào?  Chuyển giao từ AP cũ sang mới? Thời điểm chuyển AP mới 03/10/2011 @Hà Quốc Trung 2011 11  Có thể do mạng quyết định hoặc do máy quyết định  Căn cứ vào  tín hiệu (SNR)  tải của AP (cũ) Lựa chọn AP mới 03/10/2011 @Hà Quốc Trung 2011 12  Có thể có nhiều khả năng lựa chọn AP mới  Tiêu chí lựa chọn  Tải của AP (mới)  Tín hiệu SNR  Hướng chuyển động của thiết bị  Độ phức tạp cao Thiết lập kênh truyền với AP mới 03/10/2011 @Hà Quốc Trung 2011 13  Thỏa thuận  Thiết lập kênh truyền (hướng kết nối)  Tốc độ tải lên, tải xuống  Xác định địa chỉ IP  ....  Xác định các tài nguyên cần thiết cho kênh truyền tin: Channel allocation  Phức tạp, liên quan đến chi phí chung của cả hệ thống  Cần có cơ chế phân chia tài nguyên Chuyển giao kết nối từ AP cũ sang AP mới 03/10/2011 @Hà Quốc Trung 2011 14  Chuyển thẳng đến AP mới  Chuyển đến AP cũ sau đó được chuyển tiếp tới AP mới  Cùng lúc => Soft Handoffs, vd CDMA  Tuần tự => Hard Handoffs, vd GSM  Trường hợp giao thức hướng kết nối cần duy trì được kết nối (tầng giao vận) 03/10/2011 @Hà Quốc Trung 2011 15 Quản lý di động=quản lý vị trí+chuyển giao 2. Nguyên lý, kỹ thuật quản lý vị trí Quản lý bởi 1 nhà đăng ký Quản lý theo vùng Sao lưu thông tin vị trí 03/10/2011 @Hà Quốc Trung 2011 16 I. Quản lý một nhà đăng ký 03/10/2011 @Hà Quốc Trung 2011 17  Single Home Location Registrar  Ít dùng trong thực tế  Cho phép nắm được nguyên lý hoạt động của các Home Registrar  Thành phần hệ thống  Các AP  Các thiết bị di động  Home Location Registrar Thao tác đăng ký 03/10/2011 @Hà Quốc Trung 2011 18 Đăng ký khi chuyển cell 03/10/2011 @Hà Quốc Trung 2011 19 Tìm kiếm m trường hợp thành công 03/10/2011 @Hà Quốc Trung 2011 20 Tìm kiếm m Trường hợp không thành công 03/10/2011 @Hà Quốc Trung 2011 21 Giải pháp 1 03/10/2011 @Hà Quốc Trung 2011 22 - Bổ sung thêm các thông tin cho từng thiết bị di động trên HLR: - 𝑡𝑢 : thời gian cập nhật cuối cùng - TTL : thời gian có hiệu lực của liên kết - TTL nhỏ: giảm xác suất không tìm thấy - Vấn đề: - khi thời gian vượt quá TTL, HLR sẽ không có thông tin về m - Giải pháp - Cập nhật thông tin về m định kỳ chu kỳ 𝑡𝑝 nào đó nhỏ hơn TTL - Số lượng thông báo cập nhật vị trí sẽ tăng lên - Chi phí tìm kiếm giảm. - Xác suất tìm thấy tăng Giải pháp 2 03/10/2011 @Hà Quốc Trung 2011 23  Nếu không tìm thấy m trong cell c, (m,c) có ở HLR  Tìm kiếm các cell k-lân cận (bằng quảng bá)  k tăng:  Xác suất tìm thấy tăng  Thời gian tìm tăng  Chi phí quảng bá trong cell cao  𝑘 = 𝑣𝑚 ∗ 𝑡𝑝: khoảng cách tối đa mà nút có thể di chuyển trong thời gian cập nhật Quản lý bằng HLR 03/10/2011 @Hà Quốc Trung 2011 24  Tất cả các thao tác cập nhật đều chạy qua AP và HLR  AP chịu trách nhiệm về cell, HLR chịu trách nhiệm cả hệ thống  HLR quá tải  Trễ cập nhật và tìm kiếm tăng  HLR sập=> tê liệt cả hệ thống  => sử dụng nhiều HLR  Phân tán, sao lưu dữ liệu, tổ chức các HLR (phẳng, phân cấp, ...)  Thực tế: GSM II. Quản lý vị trí theo vùng 03/10/2011 @Hà Quốc Trung 2011 25  Tập hợp các cell tạo thành một vùng  Vùng đăng ký của cells: Registration Area /Location Area  Chi phí cập nhật thông tin giảm  Khi dịch chuyển giữa các AP cùng một LA/RA không cần cập nhật về HLR  Chi phí tìm kiếm tăng  Phạm vi tìm kiếm rộng hơn (vài cell của AP) MH BS MSS Cập nhật và tìm kiếm với 01 HLR 03/10/2011 @Hà Quốc Trung 2011 26 Cập nhật và tìm kiếm với 1 HLR 03/10/2011 @Hà Quốc Trung 2011 27  Cập nhật thông tin  Định kỳ, khi đăng ký, khi chuyển giao  Tương tác giữa RA và HLR  Tìm kiếm  Tại HLR: yêu cầu=> trả lời (điểm-điểm)  Tại AP: yêu cầu=> trả lời (quảng bá)  Các thành phần tham gia  Mobile, HLR, RA, AP  Phân phối các chức năng giữa các thành phần  Trường hợp nhiều HLR? 03/10/2011 @Hà Quốc Trung 2011 28 Tìm kiếm-nhiều HLR HLR1 HLR2 Có m n Tìm kiếm-nhiều HLR 03/10/2011 @Hà Quốc Trung 2011 29  Nút n tìm nút m  Nếu m có trong cùng một HLR => như đã thực hiện ở trên  Nếu m không trong cùng một HLR => kết nối với HLR 2  Vấn đề  Nút m dịch chuyển và kết nối với 𝐴𝑃 ∈ 𝐻𝐿𝑅2  Giải pháp 1  m đăng ký với HLR2, HLR2 thông báo với tất cả các nút có liên quan về sự thay đổi này  Thao tác toàn cục: chi phí cập nhật cao  Không ảnh hưởng đến quá trình tìm kiếm  Giải pháp 2  m đăng ký với HLR2, HLR2 thông báo với HLR1 về việc m đang thuộc HLR2  Các nút khác khi tìm m được HLR1 yêu cầu để kết nối với HLR2  Chi phí cập nhật nhỏ, chi phí tìm kiếm tăng Nhiều hơn 2 HLR 03/10/2011 @Hà Quốc Trung 2011 30  Nút m cập nhật thông tin khi đăng ký với LR mới  Nút n kết nối với HLR của m để nhận thông tin về LR đang quản lý m (VLR-Visiting location registrar)  Xuất hiện tương tranh giữa quá trình tìm kiếm và quá trình đăng ký  Có khả năng tìm kiếm sai (n đuổi theo m)  Giảm thời gian cập nhật, tăng thời gian tìm kiếm  Giải pháp 1  Forwarding pointer: Nút m khi chuyển giao để lại địa chỉ của mình ở LR cũ  Giải pháp 2  Cập nhật động thông tin về vị trí  Theo thời gian, theo vị trí, theo khoảng cách III. Sao lưu thông tin vị trí 03/10/2011 @Hà Quốc Trung 2011 31  Tăng tốc độ tìm kiếm  Tăng khả năng sẵn sàng của hệ thống  HLR bị sự cố=> tất cả các nút được quản lý bởi HLR không truy cập được  Các bài toán cần giải quyêt  Số lượng sao lưu (toàn bộ, một phần)  Sao lưu tại VLR của nút di động  Mô hình phẳng  Mô hình phân cấp Sao lưu tại VLR của nút 03/10/2011 @Hà Quốc Trung 2011 32  Các yêu cầu tìm kiếm của nút n đi qua VLR của n  VLR có thể tổng hợp các yêu cầu kết nối theo nút m, từ đó xác định liệu vị trí của m có thể được lưu lại hay không  Khi tìm kiếm thông tin,  nếu không có=> thực hiện tìm kiếm như thông thường  Nếu có => thực hiện truy cập  Nếu không thành công: xóa bộ nhớ đệm, thực hiện tìm kiếm lại  Cơ chế đệm “lười”. Thời gian và chi phí tìm kiếm tăng khi có cache miss. Sao lưu tại VLR của nút 03/10/2011 @Hà Quốc Trung 2011 33  Cơ chế đệm tích cực  Quản lý danh sách các LR đang lưu trữ thông tin về m  Khi m chuyển đổi vị trí: cung cấp thông tin cho tất cả các LR  Giảm chi phí tìm kiếm  Tăng chi phí cập nhật  Bài toán  Thông tin về m lưu trữ trên LR nào  Khi nào cần lưu trữ thông tin về m Mô hình phẳng 03/10/2011 @Hà Quốc Trung 2011 34 Mô hình phân cấp 03/10/2011 @Hà Quốc Trung 2011 35 3. Handoffs I. Khái niệm II. Thiết lập kênh III. Chuyển giao liên kết 03/10/2011 @Hà Quốc Trung 2011 36 I. Khái niệm 03/10/2011 @Hà Quốc Trung 2011 37  MS chuyển từ một vùng phủ sóng sang vùng phủ sóng khác, trong khi đang trao đổi thông tin  Liên kết vật lý với BS (AP) cũ được thay thế bằng liên kế với BS (AP) mới  Roaming  MS chuyển từ một hệ thống sang một hệ thống khác Các vùng bao phủ 03/10/2011 @Hà Quốc Trung 2011 38 Hệ thống thông tin cá nhân (Personal Communication Network, vd GSM) MSC region MSC region (MSC) Mobile Switch region Location area BSC BSC Location area BTS BTS Vùng bao phủ của BS 03/10/2011 @Hà Quốc Trung 2011 39  Phụ thuộc vào nhiều yếu tố khác nhau  Địa lý, ăng ten, ...  Tại ranh giới giữa các vùng bao phủ  Tín hiệu từ các BS hàng xóm tăng  Tín hiệu từ BS hiện tại giảm  Chi phí chuyển giao  Đắt, đặc biệt với các vùng bao phủ nhỏ  Vùng bao phủ nhỏ  Tăng khả năng sẵn sàng của hệ thống  Giảm tiêu thụ điện năng của các thiết bị di động  Các vấn đề  Phát hiện, thiết lập kênh, chuyển đổi liên kết II. Phát hiện chuyển giao 03/10/2011 @Hà Quốc Trung 2011 40  Vì sao cần phát hiện quá trình chuyển giao  Thực thể nào sẽ khởi tạo quá trình chuyển giao  Dựa vào các thông số của liên kết  WEI (Word Error Indicator)  RSSI (Receiving Signal Strength Indicator)  QI (Quality Indicator) 3 cách phát hiện chuyển giao 03/10/2011 @Hà Quốc Trung 2011 41  Được điều khiển bởi thiết bị  Thiết bị theo dõi liên tục trạng thái của liên kết  Khi điều kiện chuyển giao thỏa mãn, khởi động quá trình chuyển giao  Được điều khiển bởi mạng  Các AP xung quanh giám sát, đo lường chất lượng của kênh kết nối với MS  Khi điều kiện thỏa mãn, khởi động quá trình chuyển giao  Điều khiển bởi mạng, có sự hỗ trợ của thiết bị  Theo yêu cầu của mạng, MS đo đạc chất lượng kênh truyền và báo về  Căn cứ vào kết quả, mạng khởi động quá trình chuyển giáo Quá trình chuyển giao điều khiển bởi thiết bị 03/10/2011 @Hà Quốc Trung 2011 42 Quá trình chuyển giao điều khiển bởi mạng 03/10/2011 @Hà Quốc Trung 2011 43  BS giám sát chất lượng tín hiệu từ MS  Khi chất lượng tín hiệu thấp => MSC thực hiện chuyển giao  Hỏi tất cả các BS xung quanh về chất lượng tín hiệu của MS  Chọn một BS, thông báo cho MS và BS mới  Nhược điểm  Tải cho MSC  Số lượng thông báo lớn  Thời gian chuyển giao lớn MCHO/MAHO-NCHO MAHO-NCHO MCHO 03/10/2011 @Hà Quốc Trung 2011 44  Yêu cầu chuyển giao được gửi trên liên kết cũ (chất lượng thấp, => fail)  MS không nhận được thông báo=> quá trình chuyển giao lỗi  Yêu cầu chuyển giao được gửi trên liên kết mới (chất lượng cao?)  Không có thông tin điều khiển được gửi qua liên kêts III. Thiết lập kênh 03/10/2011 @Hà Quốc Trung 2011 45  Sử dụng tối ưu hạ tầng truyền thông đảm bảo chất lượng dịch vụ  Cơ chế chuyển giao  Cơ sở: không ưu tiên  Kênh đặt trước  Hàng đợi ưu tiên  Sub rating Ngắt kết nối bắt buộc 03/10/2011 @Hà Quốc Trung 2011 46  Chặn kết nối  Yêu cầu thiết lập kết nối không thành công  Không có kênh rỗi trên AP mới dành cho MS  Ngắt kết nối bắt buộc  Yêu cầu chuyển giao không thành công  Không có kết nối rỗi trên AP mới cho MS đang có kết nối với AP cũ  Các yếu tố hiệu năng  Chất lượng dịch vụ  Băng thông sử dụng  Độ phức tạp của thuật toán  Số lượng tìm kiếm trong CSDL Thiết lập kênh cơ sở 03/10/2011 @Hà Quốc Trung 2011 47 Thiết lập kênh đặt trước 03/10/2011 @Hà Quốc Trung 2011 48 Hàng đợi ưu tiên 03/10/2011 @Hà Quốc Trung 2011 49 Thay đổi điểm đánh giá 03/10/2011 @Hà Quốc Trung 2011 50 III. Chuyển giao liên kết 03/10/2011 @Hà Quốc Trung 2011 51  Gỡ bỏ liên kết cũ  Thiết lập liên kết mới  Thủ tục chuyển giao liên kết  Cứng  Mềm  Nội BTS  Liên BTS  Nội BSC  Liên BSC  Liên hệ thống Các loại chuyển giao 03/10/2011 @Hà Quốc Trung 2011 52 Liên BS 03/10/2011 @Hà Quốc Trung 2011 53 Liên MSC 03/10/2011 @Hà Quốc Trung 2011 54 Tối ưu 03/10/2011 @Hà Quốc Trung 2011 55 Chuyển giao cứng 03/10/2011 @Hà Quốc Trung 2011 56  MS chỉ kết nối với 1 BS  Trao đổi thông tin của MS bị ngắt quãng Chuyển giao mềm 03/10/2011 @Hà Quốc Trung 2011 57  MS có thể kết nối với nhiều AP (BS)  BS sử dụng chung giải tần  BS đồng bộ lẫn nhau  Hệ thống có khả năng “trộn” các thông tin từ nhiều BS  => rất phức tạp