Vehicular ad hoc network (VANET) is a special case of mobile networks, where vehicles equipped with computing/communicating devices (called "smart vehicles") are the mobile wireless nodes. However, the movement pattern of these mobile wireless nodes is no more random, as in case of mobile networks, rather it is restricted to roads and streets. Vehicular networks have hybrid architecture; it is a combination of both infrastructure and infrastructure-less architectures. The direct vehicle to vehicle (V2V) communication is infrastructure-less or ad hoc in nature. Here the vehicles traveling within communication range of each other form an ad hoc network. On the other hand, the vehicle to infrastructure (V2I) communication has infrastructure architecture where vehicles connect to access points deployed along roads. These access points are known as road side units (RSUs) and vehicles communicate with other vehicles/wired nodes through these RSUs. To provide various services to vehicles, RSUs are generally connected to each other and to the Internet. The direct RSU to RSU communication is also referred as I2I communication. The success of VANET depends on the existence of pervasive roadside infrastructure and sufficient number of smart vehicles. Most VANET applications and services are based on either one or both of these requirements. A fully matured VANET will have pervasive roadside network and enough vehicle density to enable VANET applications. However, the initial deployment stage of VANET will be characterized by the lack of pervasive roadside infrastructure and low market penetration of smart vehicles. It will be economically infeasible to initially install a pervasive and fully networked iv roadside infrastructure, which could result in the failure of applications and services that depend on V2I or I2I communications. Further, low market penetration means there are insufficient number of smart vehicles to enable V2V communication, which could result in failure of services and applications that depend on V2V communications. Non-availability of pervasive connectivity to certification authorities and dynamic locations of each vehicle will make it difficult and expensive to implement security solutions that are based on some central certificate management authority. Nonavailability of pervasive connectivity will also affect the backend connectivity of vehicles to the Internet or the rest of the world. Due to economic considerations, the installation of roadside infrastructure will take a long time and will be incremental thus resulting in a heterogeneous infrastructure with non-consistent capabilities. Similarly, smart vehicles will also have varying degree of capabilities. This will result in failure of applications and services that have very strict requirements on V2I or V2V communications. We have proposed several solutions to overcome the challenges described above that will be faced during the initial deployment stage of VANET. Specifically, we have proposed:  A VANET architecture that can provide services with limited number of heterogeneous roadside units and smart vehicles with varying capabilities.  A backend connectivity solution that provides connectivity between the Internet and smart vehicles without requiring pervasive roadside infrastructure or large number of smart vehicles.  A security architecture that does not depend on pervasive roadside infrastructure or a fully connected V2V network and fulfills all the security requirements. v  Optimization solutions for placement of a limited number of RSUs within a given area to provide best possible service to smart vehicles. The optimal placement solutions cover both urban areas and highways environments