Báo Cáo Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA QUỐC TẾ & ĐÀO TẠO SAU ĐẠI HỌC
BÁO CÁO TIỂU LUẬN
MÔN HỌC: KỸ THUẬT TỐI ƯU
CHUYÊN ĐỀ:
ĐIỀU KHIỂN LUỒNG THÔNG MINH THEO KHUÔN KHỔ LÝ THUYẾT TRÒ CHƠI
​​

MỞ ĐẦUTrong những năm gần đây, luồng điều khiển và quản lý mạng trong các mạng tốc độ cao đã thu hút được sự chú ý nhiều bởi các nhà nghiên cứu trong lĩnh vực viễn thông. Trong các môi trường mạng quy mô lớn với độ phức tạp cao, kiểm soát phân cấp và ra quyết định được yêu cầu. Nhiều tài liệu nghiên cứu liên quan với phương pháp tiếp cận đa ngành để mô hình hóa, kiểm soát và quản lý mạng từ một điểm tính toán thông minh xuất hiện trong các tạp chí viễn thông quan trọng hàng năm. Tuy nhiên, chỉ một vài trong số đó tập trung vào sự giống nhau giữa phân bổ nguồn lực trong một môi trường mạng và cơ chế thị trường trong lý thuyết kinh tế. Bằng cách tham gia một cách tiếp cận kinh tế (thị trường và dựa trên lý thuyết trò chơi) trong việc điều khiển luồng của một mạng lưới thông tin liên lạc, chúng ta tìm kiếm các giải pháp mà việc tạo ra trí thông minh và quyết định được phân phối, và do đó khả năng mở rộng, và mục tiêu sử dụng hiệu quả hơn và công bằng trong chia sẻ kết quả các tài nguyên từ các động lực thị trường gây ra.
Không giống như các phương pháp tiếp cận khác được phân cấp, tập trung chính của chúng tôi là sử dụng trí thông minh tính toán để mô hình hóa các agents quyết định phân phối và nghiên cứu hành vi động theo khuôn khổ của lý thuyết trò chơi trong phân bổ tài nguyên mạng. Bằng cách xem một mạng lưới như là một bộ sưu tập các nguồn tài nguyên mà người dùng được cạnh tranh, nghiên cứu của chúng tôi nhằm mục đích tìm kiếm các thuật toán hiệu quả, phân cấp, dẫn đến kiến ​​trúc mạng lưới cung cấp rõ ràng chất lượng của dịch vụ (QoS) đảm bảo, vấn đề quan trọng trong các mạng đa phương tiện tốc độ cao.
Có một số dự án nghiên cứu song song của các tổ chức khác nhau đối với vấn đề phức tạp này. COMET tại Ðại học Columbia (http://comet.columbia.edu/research/) gọi là quyết định phân cấp làm quá trình cho trò chơi mạng. Sử dụng phương pháp tiếp cận trò chơi mạng, họ có ý định để giải quyết những vấn đề quan trọng của giá cả từ mặt đất lên mạng từ các điểm kỹ thuật của view, chứ không phải là có, cũng như trong các mạng truyền thông hiện có, một cơ cấu giá nhất thiết phải tùy tiện áp đặt bài trên thực tế. Bằng cách tham gia một cách tiếp cận thị trường dựa trên hệ thống phân phối, Michigan Marx Project (http://ai.eecs.umich.edu/MARX/), tìm kiếm giải pháp để cho phép phân bổ nguồn lực thích ứng của các hệ thống thông tin quy mô lớn. Một bộ sưu tập rất hữu ích của liên kết và các nguồn lực khác nhau về kinh tế mạng và các vấn đề liên quan được duy trì tại Berkeley của HR Varian (http://www.sims.berkeley.edu/resources/infoecon/Networks.html). Tuy nhiên, có một số ít tác phẩm được công bố mà cố gắng để giải quyết điều khiển nhận cuộc gọi cũng như quản lý lưu lượng trong các mạng viễn thông từ một quan điểm lý thuyết của trò chơi xem bằng cách sử dụng trí thông minh tính toán. Chúng tôi tổ chức công việc của chúng tôi thành hai chương. Chương đầu tiên là giới thiệu các kỹ thuật chẩn đoán trong viễn thông, chương thứ hai bao gồm hai phần: Phần đầu tiên giành riêng cho điều khiển nhận kết nối (CAC) xử lý trong mạng lưới máy ATM. Bằng cách năng động CAC như một vấn đề chia sẻ tài nguyên, chúng tôi sử dụng một mô hình trò chơi hợp tác với các hình thức sản phẩm của một sự kết hợp một số sở thích của người dùng để tối ưu hóa khả năng chặn cuộc gọi trong khi duy trì QoS đàm phán ở giai đoạn thiết lập cuộc gọi. Sau khi thu được những hình thức sản phẩm của các chức năng ưu tiên người sử dụng, chúng tôi sử dụng một thuật toán di truyền để tối ưu hóa hàm mục tiêu này để duy trì chia sẻ công bằng trong giai đoạn truyền tải lưu lượng truy cập. Phần thứ hai của các mô hình làm việc của chúng tôi không hợp tác hành vi người dùng trong quá trình phân bổ tài nguyên theo một khuôn khổ bán đấu giá tổng quát. Chúng tôi đề xuất một quy tắc bán đấu giá tối ưu dẫn đến trạng thái cân bằng trong một trò chơi năng động lặp đi lặp lại. Chúng tôi cũng sử dụng các mạng thần kinh để mô hình hóa các chiến lược người sử dụng trong đấu thầu, và một thời gian ngắn thảo luận về sự hình thành của kiến ​​thức phổ biến trong các trò chơi lặp đi lặp lại và hiệu quả phân bổ. Các đặc điểm phổ biến cho hai phần này là chúng tôi sử dụng các kỹ thuật tình báo một số tính toán để giải quyết các mô hình phức tạp và các vấn đề tối ưu hóa trong phân bổ tài nguyên.

MỤC LỤC
MỞ ĐẦU 5
CHƯƠNG 1: GIỚI THIỆU CÁC KỸ THUẬT CHẨN ĐOÁN TRONG VIỄN THÔNG . 7
I. TỐI ƯU HÓA TRONG VIỄN THÔNG . 7
II. VẤN ĐỀ ĐỘNG VÀ SỰ THÍCH ỨNG . 7
III. MÔ HÌNH CÁC KỸ THUẬT CHẨN ĐOÁN(HEURISTIC). 8
1. Tìm kiếm cục bộ. 9
1.1 Phương pháp luyện thép(Simulated Annealing). 10
1.2 Tìm kiếm Tabu. 11
1.3 Tìm kiếm cục bộ Artful 12
2. Tìm kiếm dựa trên quần thể. 14
IV. KỸ THUẬT TÍNH TOÁN THÍCH NGHI. 16
1. Thuật toán Nơ-ron. 17
2. Logic mờ. 19
3. Lý thuyết trò chơi 20
V. TÓM TẮT CHƯƠNG 1. 21
CHƯƠNG 2: ĐIỀU KHIỂN LUỒNG THÔNG MINH THEO KHUÔN KHỔ LÝ THUYẾT TRÒ CHƠI 21
I. ĐIỀU KHIỂN NHẬN KẾT NỐI DỰA TRÊN MÔ HÌNH LÝ THUYẾT TRÒ CHƠI TRONG CÁC MẠNG LƯỚI ATM . 22
1. Sơ lược các điều khiển tắc nghẽn trong mạng ATM . 22
2. Mô hình trò chơi hợp tác cho phân bổ băng thông động. 24
3. Điều khiển nhận cuộc gọi với thuật toán di truyền. 30
4. Tóm tắt điều khiển nhận kết nối bằng cách sử dụng trò chơi hợp tác. 33
II. THIẾT KẾ BÁN ĐẤU GIÁ TỐI ƯU CHO CHIA SẺ TÀI NGUYÊN 33
1. Phân bổ tài nguyên như một vấn đề thiết kế bán đấu giá. 33
2. Các định nghĩa cơ bản và giả định cho thiết kế bán đấu giá tối ưu. 35
3. Các cơ chế bán đấu giá khả thi 37
4. Thiết kế bán đấu giá tối ưu cho quá trình phân phối tài nguyên phân chia tùy ý. 40
5. Mô phỏng nghiên cứu cá nhân tới mẫu kiến thức phổ biến. 43
III. KẾT LUẬN 47
IV. PHỤ LỤC 48
1. Chứng minh bổ đề 1: 48
2. Chứng minh bổ đề 2: 49
3. Chứng minh định lý. 51